나무 탈출

시간 제한2초메모리 제한512 MB

요약

루트가 있는 트리에서 각 리프에 말이 하나씩 놓인 상태로 시작해, 두 사람이 번갈아 말을 부모로 옮기고 루트에 닿으면 제거하는 게임에서 선수가 이길 수 있는지 판정한다.

난이도: 어려움10점 중 9점
유형: 게임 이론, 트리, DFS, 동적 계획법
정답자: 아직 제출이 없습니다

문제

성원이가 먼저 시작하고 형석이가 나중에 시작하며, 두 사람은 나무 모양의 게임판 위에서 번갈아 가면서 게임말을 움직인다. 게임판은 $N$ 개의 정점에 $1$ 부터 $N$ 까지 번호가 붙은 트리이다. $1$ 번 정점은 루트 노드이며, 루트를 기준으로 부모 자식 관계가 정해진다. 자식이 없는 노드를 리프 노드라고 한다.

처음에는 모든 리프 노드에 게임말이 하나씩 놓여 있다. 차례가 오면 판 위에 있는 게임말 중 하나를 골라 그 말이 있던 노드의 부모 노드로 옮긴다. 이때 한 노드에 여러 개의 말이 함께 놓일 수 있다. 옮긴 말이 루트 노드에 도착하면 그 말은 즉시 판에서 제거한다. 말을 옮긴 뒤에는 차례를 상대에게 넘긴다. 판 위에 말이 하나도 없어서 고를 수 없는 사람이 진다.

게임판의 모양만 보고 성원이가 최선을 다했을 때 이길 수 있는지를 판단하는 프로그램을 작성하라.

입력

첫째 줄에 트리의 정점 개수 $N$ ( $2 \le N \le 500{,}000$ )이 주어진다.

둘째 줄부터 $N-1$ 줄에 걸쳐 간선 정보가 주어진다. 각 줄에는 두 자연수 $a$ , $b$ ( $1 \le a, b \le N$ , $a \ne b$ )가 주어지며, 이는 정점 $a$ 와 정점 $b$ 사이에 간선이 있음을 뜻한다.

출력

성원이가 최선을 다했을 때 이길 수 있으면 Yes, 그렇지 않으면 No를 출력한다.

예제3

예제 1
입력
```
2
2 1
```
예상 출력
```
Yes
```
예제 2
입력
```
4
1 2
2 3
2 4
```
예상 출력
```
No
```
예제 3
입력
```
8
8 1
1 4
7 4
6 4
6 5
1 3
2 3
```
예상 출력
```
No
```