ECOO '21 Practice P5 - Rockets
View as PDFNote 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?
Input Specification
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.
Output Specification
Output Let's play >:) if you can win the game, and NOU >:( if she will beat you.
Subtasks
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 3Sample 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 2Sample Output 2
NOU >:(Sample Input 3
8
1 2
1 3
2 4
2 5
3 6
6 7
6 8
1 3Sample 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 
.
Comments