Note this problem was originally intended for the cancelled 2020 Girls Invitational Competition.
Evanette Zhang is giving away Rocket candies, but only if you play and win a game against her. She arranges of her Rocket candies to form connections between points. You observe that the points are completely connected, there are no cycles, and a connection always consists of a single Rocket between two points. Evanette starts the game by taking away a Rocket from the arrangement. You then must take a Rocket that was adjacent to the one she just took. You will continue alternating turns until there are no more valid rockets to take, in which the game is over and the loser is the person that cannot take a Rocket. If you beat her, you get to keep all the Rockets in the arrangement. Rockets are of little value to you, (tootsie rolls are far superior) so you'll only play her game if you know you can win. Can you determine if you will win the game given her first move if both of you play optimally?
The first line of input will contain one integer, , the number of points. We will guarantee that in all test cases.
The next lines will each contain two integers and , indicating a Rocket exists between these two points.
The last line of input will contain two integers and , indicating that the Rocket between these two points is the one Evanette took. It is guaranteed that this Rocket exists.
Let's play >:) if you can win the game, and
NOU >:( if she will beat you.
Subtask 1 [29%]
For each , there will be a rocket connecting point and point .
Subtask 2 [71%]
No further constraints.
Note: you do not need to pass sample 2 or 3 for the first subtask.
Sample Input 1
5 1 2 2 3 3 4 4 5 2 3
Sample Output 1
Let's play >:)
Explanation For Sample 1
If you take the Rocket connecting points and , then she can take the Rocket connectings points and . You cannot take any rockets, so you would lose. However, if you took the Rocket connecting points and , then she will have no Rockets to take, and you will win.
Sample Input 2
8 1 2 1 3 2 4 2 5 3 6 6 7 6 8 1 2
Sample Output 2
Sample Input 3
8 1 2 1 3 2 4 2 5 3 6 6 7 6 8 1 3
Sample Output 3
Let's play >:)
Explanantion for Sample 3
Evanette initially takes the Rocket between points and (marked in green with the number ). Then, you can take the Rocket between and (marked in red with the number ). Evanette will either choose the Rocket between and or the one betwwen and . In both cases, however, you would simply take the other one that she did not take, and she would not be able to take any more Rockets. In this case, you would be guaranteed to win. In the diagram, we show that if she takes the Rocket between and , you would take the one between and .