Lumberjack#4808
Two players play the following game: there is a tree with a designated root vertex. Players take turns making moves. In each move, a player cuts a branch (removes an edge), and out of the two resulting connected components, only the component containing the root remains; the other component is discarded and no longer participates in the game. The player who cannot make a move loses.
Determine whether the first player can win the game, and if so, provide any of their winning moves.
The first line contains two integers and — the number of vertices in the tree and the number of the root vertex respectively (1 < N \leq 100\,000, 1 \leq R \leq N). The following N - 1 lines each contain two integers describing an edge between two vertices.
Output a single integer: or — the player who will win under optimal play. If the first player can win, also output any of their winning moves: the index in the input (from to N - 1) of an edge that should be cut on their first move.
Example 1