Darth Vader and 3PO on a Tree!
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!
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.
In a single line print who will win. If no one can collect less coins than other, print “Draw”.
4 2 3 4 2 2 1
5 1 2 3 1 4 3 3 5
5 1 2 3 1 2 4 5 3
himuhasibHasib is passionate about sport programming and artificial intelligence. He was an IOI participant through years 2013-2015. He qualified to ACM-ICPC World Finals 2016. He studies at North South University. →