Two players are playing a strategic game on a graph. The graph consists of vertices, numbered from to , and edges connecting them. Between any two vertices there exists exactly one path.
Players make moves in turn. Each move consists of the following: the player marks the current vertex as "visited", chooses an adjacent vertex, and moves there. After the move, the vertex from which the player just moved is removed from the graph along with all its edges. Then the other player makes their move. The player who cannot make a move loses.
Write a program that, given the initial graph and the starting vertex number, determines who wins if both players play perfectly (each chooses the best move).
The first line contains two integers: and separated with a space. Here is the number of vertices (n \leq 1000) and is the number of the starting vertex (1 \leq k \leq n). The next n-1 lines contain pairs of integers separated with a space. These integers are numbers of vertices connected by an edge (all edges are bidirectional and are mentioned only once). Each vertex is connected to at most others.
If the player who starts the game wins, the program should write First player wins moving to where is the number of the vertex to which the player should move first. If there are several such vertices, the program should choose the one with the minimal number. Otherwise the program should write First player loses.
Example 1