Tree Escape

Time limit2sMemory limit512 MB

Summary

On a rooted tree where each leaf starts with one piece, players alternately move a piece to its parent and remove it at the root; decide if the first player wins.

Level: Hard9 of 10
Topics: Game theory, Tree, DFS, Dynamic programming
Solved: No attempts yet

Problem

Seongwon moves first and Hyeongseok moves second in a board game played on a tree. The board is a tree with $N$ vertices numbered from $1$ to $N$ . Vertex $1$ is the root node, and the parent child relation is defined with respect to the root. A node without children is called a leaf node.

The two players alternate moving one piece, with Seongwon to move first. At the start, every leaf node holds exactly one piece. On your turn, choose one piece on the board and move it to the parent of the node it stands on. Several pieces may share one node. If the moved piece reaches the root node, remove it from the board at once. After moving, pass the turn to the opponent. A player who cannot choose a piece because the board holds no pieces loses.

Write a program that looks only at the shape of the board and decides whether Seongwon can win with optimal play.

Input

The first line gives the number of vertices $N$ ( $2 \le N \le 500{,}000$ ).

Each of the following $N-1$ lines describes an edge. Each line gives two natural numbers $a$ and $b$ ( $1 \le a, b \le N$ , $a \ne b$ ), meaning vertices $a$ and $b$ are joined by an edge.

Output

Print Yes if Seongwon can win with optimal play, and print No otherwise.

Examples3

Example 1
Input
```
2
2 1
```
Expected output
```
Yes
```
Example 2
Input
```
4
1 2
2 3
2 4
```
Expected output
```
No
```
Example 3
Input
```
8
8 1
1 4
7 4
6 4
6 5
1 3
2 3
```
Expected output
```
No
```