A tree game P61396


Statement
 

pdf   zip

thehtml

Consider this game for two players with a tree with n nodes: By turns, the current player must choose a (non-empty) subtree and remove it. The player that removes the root loses the game.

Assuming perfect play, can you tell if the player to play will win the game? If so, can you find a winning move?

Input

Input consists of several cases, each with n, followed by the n − 1 edges x y of the tree, meaning that x is the parent of y. Assume 1 ≤ n ≤ 105, and that the n − 1 given edges define a tree rooted at 1 with the nodes labelled from 1 to n.

Output

For every tree, print ‘L’ if the position is losing. Otherwise, print the root of the subtree that should be removed. If there is more than one winning move, choose the smallest one.

Public test cases

  • Input

    4  1 4  4 3  3 2
3  1 2  1 3
4  1 2  1 3  1 4
6  3 4  1 5  5 3  1 6  3 2
7  1 7  5 3  1 5  7 4  7 6  5 2

    Output

    4
L
2
3
L
    • Information
    Author
    Ivan Geffner
    Language
    English
    Official solutions
    C++
    User solutions
    C++