Mock CCC '19 Contest 1 S5 - Tree Game

View as PDF

Submit solution

Points: 17
Time limit: 2.0s
Memory limit: 128M

Problem types

You are given a tree with N nodes and N-1 edges. Initially, each node is uncolored.

You and your best friend are playing a game by painting the nodes. In this game, you will alternately perform the following operation, starting with yourself:

  • Select a node that is not painted yet.
  • If it is your turn, paint the node white, otherwise paint the node black.

Then, after all the vertices are colored, the following procedure takes place:

  • Repaint every white node that is adjacent to a black node, in black.

Note that all such white nodes are repainted simultaneously, not one at a time.

If there are still one or more white nodes remaining, you win. If all the nodes are now black, your friend wins. Determine the winner of the game, assuming that you will both play optimally.

Input Specification

The first line will contain the integer N\ (1 \le N \le 10^5).

The next N-1 lines will each contain two integers, a_i, b_i\ (1 \le a_i, b_i \le N), indicating nodes a_i and b_i are connected by an edge. It is guaranteed the entire tree is connected.

Output Specification

Output First if you win, and Second if your friend wins.


There are no subtasks for this problem.

Sample Input 1

1 2
2 3

Sample Output 1


Sample Input 2

1 2
2 3
2 4

Sample Output 2


Sample Input 3

1 2
2 3
3 4
2 5
5 6

Sample Output 3



There are no comments at the moment.