24896번 - 르블랑의 트리 순회

$N$개의 정점으로 이루어진 트리가 있다. 르블랑은 이 트리를 순회하려고 한다.

임의의 정점에서 출발해 유한 번의 행동으로 모든 간선을 정확히 한 번씩 방문하는 과정을 "적절한 순회"라고 한다. 르블랑은 정점 위에 있을 때마다 다음의 다섯 가지 행동 중 하나를 할 수 있다.

1. 현재 정점에 인접한 간선 하나를 골라 방문하고, 간선을 따라 건너편 정점으로 이동한다.
2. 트리에 노란색 체크포인트가 없을 경우, 현재 정점에 노란색 체크포인트를 생성한다.
3. 트리에 노란색 체크포인트가 있을 경우, 노란색 체크포인트로 순간이동하고 노란색 체크포인트를 제거한다.
4. 트리에 보라색 체크포인트가 없을 경우, 현재 정점에 보라색 체크포인트를 생성한다.
5. 트리에 보라색 체크포인트가 있을 경우, 보라색 체크포인트로 순간이동하고 보라색 체크포인트를 제거한다.

위 그림들은 각각 예제 1과 예제 2의 적절한 순회 방법 중 하나이다.

처음에 트리에는 어떠한 체크포인트도 없다.

르블랑이 시작 정점을 잘 고르고 최적으로 행동한다면 적절한 순회를 할 수 있는지 알아보자.

첫째 줄에 정점의 개수 $N$이 주어진다. $(4 \leq N \leq 500,000)$

둘째 줄부터 $N-1$개의 줄에 걸쳐 각 간선이 연결하는 두 정점의 번호 $a,b$가 공백으로 구분되어 주어진다. $(1 \leq a,b \leq N,\ a \neq b)$

입력으로 주어지는 그래프는 트리이다.

주어진 트리에서 르블랑이 시작 정점을 잘 고르고 최적으로 행동했을 때 적절한 순회가 가능하면 "YES"를, 불가능하면 "NO"를 따옴표를 제외하고 출력한다.