ECOO '21 Practice P5 - Rockets

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

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 M of her Rocket candies to form connections between N 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, N (2 \le N \le 10^5), the number of points. We will guarantee that M = N-1 in all test cases.

The next M lines will each contain two integers A and B (2 \le A, B \le N), indicating a Rocket exists between these two points.

The last line of input will contain two integers C and D (2 \le C, D \le N), 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 i (1 \le i < N), there will be a rocket connecting point i and point i+1.

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 3 and 4, then she can take the Rocket connectings points 4 and 5. You cannot take any rockets, so you would lose. However, if you took the Rocket connecting points 1 and 2, 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

NOU >:(

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 1 and 3 (marked in green with the number 1). Then, you can take the Rocket between 1 and 2 (marked in red with the number 2). Evanette will either choose the Rocket between 2 and 4 or the one betwwen 2 and 5. 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 2 and 5, you would take the one between 2 and 4.


Comments

There are no comments at the moment.