J. Barnacle Game
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Darwin's biggest rival, Wallace, has challenged him to a game to determine who is the real Father of Evolution!

Being the one challenged, Darwin gets to pick the format, and so he chooses his specialty: barnacles. A barnacle can be represented as a set of $$$n$$$ segments connected together by $$$n-1$$$ ligaments with no cycles. In other words, a barnacle is a tree where segments are nodes and ligaments are edges.

The game that Darwin proposes is as follows:

  • The players alternate taking turns, with Darwin going first.
  • On the current player's turn, they will choose one ligament of the remaining barnacle and cut it.
  • Then, the other player will choose one connected component of the barnacle to keep after the cut, and discard the rest of the barnacle. This concludes the turn, and roles swap for the next round.

When a player must cut a ligament and there are no ligaments in the remaining barnacle left to cut, that player loses.

Wallace has just brought in the barnacle they will play the game on, but Darwin is not sure if he wins under optimal play from both players. Please help Darwin determine if he can win the game and keep his title as the Father of Evolution!

Input

The first line of input will contain an integer $$$n\ (1\leq n\leq 5000)$$$ — the number of segments of the barnacle.

The next $$$n-1$$$ lines will contain two integers $$$u$$$ and $$$v\ (1\leq u,v\leq n)$$$ — indicating there is a ligament between segments $$$u$$$ and $$$v$$$.

It is guaranteed the given segments form a tree.

Output

Print "I am Darwinning!" (without quotes) if Darwin wins under optimal play, or "I lost the game." (without quotes) if Wallace wins.

Examples
Input
3
1 2
2 3
Output
I lost the game.
Input
8
1 2
1 3
3 4
3 5
3 6
6 7
7 8
Output
I am Darwinning!
Note

In the first test, if Darwin cuts the 1-2 ligament, the barnacle will be split into two components {1} and {2,3}. Then, Wallace can choose the {2,3} component to keep. After Wallace cuts the 2-3 ligament, splitting the barnacle into {2} and {3}, regardless of which component Darwin chooses to keep, there will be no more ligaments for him to cut on his turn, meaning he loses. It can be shown that Darwin also loses if he starts by cutting the 2-3 ligament, so there is no way for Darwin to win.