23050번 - 데칼코마니 트리 스페셜 저지

문제

아래의 아름다운 나비를 보아라.

아름다운 나비

위 그림은 회색 점선으로 표시된 직선에 대하여 대칭을 이루고 있다. 이렇듯 선대칭을 이루는 그림을 "데칼코마니"라고 부른다.

$N$개의 정점으로 이루어진 트리에 대하여 트리 그림을 정의하자.

• 트리 그림은 원 $N$개와 선분 $(N-1)$개로 이루어져 있다.
• 하나의 원은 트리에서 하나의 정점을 의미한다. 원과 정점은 서로 일대일 대응된다.
• 하나의 선분은 트리에서 하나의 간선을 의미한다.
  • 이 선분의 양 끝 점 각각은 어떤 원의 둘레 위에 있다. 끝 점이 두 개이므로 이 조건을 만족하는 원은 두 개인데, 이 두 원을 선분의 양 끝 원이라고 부르자.
  • 이 선분의 양 끝 점을 지나는 직선은 양 끝 원의 중심을 지난다.
  • 이 선분의 양 끝 원은 간선의 양 끝의 두 정점과 서로 대응된다.
• 원은 다른 원과 점을 공유해서는 안 되며, 선분은 다른 선분이나 원과 점을 공유하지 않아야 한다. 단, 선분의 조건에 의해 어떤 선분이 양 끝 원과 양 끝 점을 공유하는 것은 허용된다.
• 모든 원의 반지름은 동일하며, 선분의 두께는 무시 가능할 정도로 아주 얇다.

다음은 트리 그림의 예시를 나타낸 것이다.

트리 그림

어떤 트리의 트리 그림 중 데칼코마니인 것이 존재한다면 이러한 트리를 데칼코마니 트리라고 부르자. 정점 $N$개로 이루어진 트리가 주어질 때, 이 트리가 데칼코마니 트리인지 판별하라.

입력

첫째 줄에 정수 $N$이 주어진다. (1ドル \le N \le 10^6$)

둘째 줄부터 $(N-1)$개의 줄에 걸쳐 트리의 간선의 정보가 주어진다. $(i+1)$번째 줄에는 $i$번째 간선의 정보를 나타내는 두 정수 $A_i,ドル $B_i$가 주어진다. 이는 $i$번째 간선이 $A_i$번 정점과 $B_i$번 정점을 서로 연결한다는 의미이다. (1ドル \le i \le N-1,ドル 1ドル \le A_i \le N,ドル 1ドル \le B_i \le N,ドル $A_i \ne B_i$)

출력

만약 주어진 트리가 데칼코마니 트리가 아니라면 첫째 줄에 "NO"를 출력한다.

만일 주어진 트리가 데칼코마니 트리라면 첫째 줄에 "YES"를 출력한다. 이후 둘째 줄에 $N$개의 정수 $C_1,ドル $\cdots,ドル $C_N$을 공백을 사이에 두고 출력한다. 이는 데칼코마니 트리 그림에서 $i$번 정점의 원과 $C_i$번 정점의 원이 서로 선대칭을 이룸을 의미한다. $(1 \le i \le N)$

트리 그림 중 데칼코마니인 것이 여러 개 존재한다면 그중 아무거나 출력해도 정답으로 인정된다.

제한

노트

네 개의 예제를 그림으로 나타내면 아래와 같다.