Lumberjack
Two players are engaged in a game involving a tree with a designated root vertex. They take turns making moves. During each turn, a player cuts a branch (removes an edge), and from the two resulting connected components, only the component containing the root remains; the other component is discarded and no longer part of the game. The player who cannot make a move loses.
Your task is to determine if the first player has a winning strategy, and if so, identify any of his winning moves.
Input
The first line of the input contains two integers, N and R, representing the number of vertices in the tree and the root vertex number, respectively (1 < N ≤ 100000, 1 ≤ R ≤ N). The following N-1 lines each contain two integers, indicating the vertices connected by each edge.
Output
Output a single integer: 1 or 2, indicating the player who will win with optimal play. If the first player can win, also output any of his winning moves, which is the index of the edge in the input file that he should cut on his first move (a number from 1 to N-1).