Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Darth Vader and 3PO on a Tree!

By himuhasib · Limits 1s, 512 MB

Did you watch Star Wars yet? No? You should in your free time.

Now back to Darth Vader and 3PO. Darth Vader and 3PO are playing a game. As you know, 3PO is the most decent robot in the world and always frightened by lightsaber. So they are playing a game on a tree! They initially choose a tree with N nodes. Then they play in turn. In each turn a player can choose a node from the given tree. In each node there are some coins. The amount of coins is equal to the distance from this node to the nearest leaf node. Same node cannot be chosen twice by any player. When any player cannot make any further move the game ends. The player who have less coins than other at the end of the game will win the game. Note that in a given tree, it’s possible that 3PO and Darth Vader has the same amount of coins.

You will be given the tree. You have to determine who will win if both players play optimally. If both player get the same amount of coin, tell us that!

Oh, almost forgot to tell you, 3PO will choose a node first, Darth Vader will choose a node next, and so on. May the force be with 3PO!

Input

In the first line of input, there will be a number N (2 ≤ N ≤ 10 5) denoting the number of nodes in the tree. In the next N-1 lines there will be a pair of number p (1 ≤ p ≤ N) and q (1 ≤ q ≤ N), denoting that there is an edge between node p and node q.

Output

In a single line print who will win. If no one can collect less coins than other, print “Draw”.

Samples

InputOutput
4
2 3
4 2
2 1
3PO
InputOutput
5
1 2
3 1
4 3
3 5
Draw
InputOutput
5
1 2
3 1
2 4
5 3
Darth Vader

Discussion

Statistics


69% Solution Ratio

fsshakkhorEarliest, Oct '16

Ruffian_SalehFastest, 0.0s

sarwarITLightest, 6.2 MB

Ruffian_SalehShortest, 753B

Submit

Login to submit

Editorial

Initially we need to find the amount of coins on each node of the given tree. To do this, initially...

Related Contests