트리 게임

시간 제한1초메모리 제한2048 MB

요약

트리가 주어질 때, 리틀 J가 라운드마다 열린 간선 하나를 닫는 상황에서 리틀 I가 칩을 1번 정점에서 차수가 1인 정점으로 옮길 수 있는지 판정합니다. 이기면 1, 지면 0을 출력합니다.

난이도: 어려움10점 중 8점
유형: 트리, 게임 이론, 그리디
정답자: 아직 제출이 없습니다

문제

리틀 I와 리틀 J가 또 게임을 하고 있다.

리틀 J가 정점이 $n$ 개인 트리를 가져왔다. 트리의 각 간선은 열림과 닫힘 두 가지 상태 중 하나이다. 처음에는 모든 간선이 열려 있다.

칩은 정점 $1$ 에 놓여 있다. 리틀 I는 칩을 움직일 수 있으며, 목표는 차수가 정확히 1인 정점으로 칩을 옮기는 것이다. 리틀 J는 간선을 닫아서 리틀 I가 차수가 정확히 1인 정점에 도달하지 못하게 한다. 정점의 차수는 간선이 열려 있든 닫혀 있든 그 정점에 연결된 간선의 개수이다.

게임은 여러 라운드로 진행되며, 각 라운드는 다음 단계로 이루어진다.

리틀 I의 목표 확인: 칩이 차수가 정확히 1인 정점에 있으면 리틀 I가 이긴다. 그렇지 않으면 2단계로 간다.
리틀 J의 행동: 리틀 J는 열려 있는 간선 하나를 영구히 닫는다. 열려 있는 간선이 없으면 이 행동은 건너뛰고 3단계로 간다.
리틀 I의 행동: 리틀 I는 칩이 있는 정점에 연결된 열린 간선 하나를 골라, 그 간선의 반대쪽 끝 정점으로 칩을 옮긴다. 그런 간선이 없으면 리틀 J가 이긴다. 그렇지 않으면 1단계부터 새 라운드가 시작된다.

두 사람이 트리의 구조를 알고 있고 매우 영리하게 행동한다고 할 때, 누가 이기는지 구하라.

입력

첫 줄에 트리의 정점 개수를 나타내는 정수 $n$ ( $1 \le n \le 10^5$ )이 주어진다.

이어서 $n - 1$ 개의 줄에 각각 간선으로 연결된 두 정점 $u$ 와 $v$ ( $1 \le u, v \le n$ )가 주어진다.

출력

리틀 I가 이기면 1을, 그렇지 않으면 0을 출력한다.

예제2

예제 1
입력
```
6
1 2
2 3
2 4
1 5
5 6
```
예상 출력
```
0
```
예제 2
입력
```
7
1 2
2 3
2 4
1 5
5 6
5 7
```
예상 출력
```
1
```