벙커

면접 대비

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

요약

노드가 n개인 트리가 주어졌을 때, 차수가 2인 정점이 있고 그 양쪽 가지의 크기가 같으며 서로 대칭인지 판별합니다.

난이도: 보통10점 중 5점
유형: 트리, 해시맵, DFS
정답자: 아직 제출이 없습니다

문제

페탸와 바샤는 스파이 놀이에 푹 빠져 있다. 오늘은 비밀 벙커와 본부를 어디에 둘지 계획하고 있다.

둘은 벙커가 정확히 $n$ 개 필요하다고 정했다. 비밀 유지를 위해 벙커에는 $1$ 번부터 $n$ 번까지 번호를 붙인다. 일부 벙커는 양방향 터널로 이어지며, 어떤 벙커에서든 다른 벙커로 가는 경로는 정확히 하나뿐이다. 어떤 벙커끼리 이어질지는 이미 정했지만, 어느 벙커를 본부로 삼을지는 정하지 못했다. 둘은 본부를 하나 고른 뒤 나머지 벙커를 같은 수만큼 나눠 가지려 한다. 이때 본부에는 터널이 정확히 두 개 이어져야 하며, 하나는 바샤의 벙커에서, 다른 하나는 페탸의 벙커에서 와야 한다.

지친 페탸는 집에 갔다. 다음 날 아침 바샤는 벙커를 점으로, 터널을 선분으로 그린 설계도를 보여 주었다. 바샤는 본부에 해당하는 점을 지나는 직선에 대해 설계도가 대칭이 되도록 본부를 골라 두었다.

페탸는 바샤가 벙커의 절반만 그렸다고 곧바로 지적했다. 그 뒤 그는 본부를 골라 이런 대칭 설계도를 그릴 수 있는지 궁금해졌다.

입력

첫 번째 줄에 벙커의 개수 정수 $n$ ( $1 \le n \le 10^5$ )이 주어진다. 이후 $n - 1$ 개의 줄에 각각 정수 $u_i$ 와 $v_i$ ( $1 \le u_i, v_i \le n, u_i \ne v_i$ )가 주어진다. 이는 $i$ 번째 터널이 잇는 벙커의 번호이다. 임의의 두 벙커 사이의 경로는 정확히 하나임이 보장된다.

출력

본부를 고를 수 있고 그러한 설계도를 그릴 수 있으면 YES를, 그럴 수 없으면 NO를 출력한다.

예제2

예제 1
입력
```
2
1 2
```
예상 출력
```
NO
```
예제 2
입력
```
3
1 2
2 3
```
예상 출력
```
YES
```