34188번 - Tri-Tree XOR 스페셜 저지

문제

정점 번호가 1,ドル 2, \cdots, N$인 $N$개 정점으로 이루어진 그래프 $A,ドル $B$가 있다고 할 때 두 그래프 사이 XOR 연산을 아래와 같이 수행한다.

• 정점 번호가 1,ドル 2, \cdots, N$인 $N$개 정점이 있고 간선이 없는 그래프 $C$를 만든다.
• 1ドル\le i<j\le N$인 모든 정수 $i,ドル $j$ 쌍에 대해 정점 $i$와 정점 $j$를 잇는 간선이 그래프 $A$와 그래프 $B$ 중 정확히 하나에만 존재한다면 그래프 $C$에서 정점 $i$와 정점 $j$를 간선으로 연결한다.

정점이 $N$개인 트리 $A$가 주어질 때 정점이 $N$개인 적당한 트리 $B$를 만들어서 $A$와 $B$의 XOR 연산 결과인 그래프 $C$가 트리가 되는 $B$가 존재하는지 확인하고, 존재한다면 가능한 트리 $B$를 하나 구해보자.

입력

첫째 줄에 트리 $A$의 정점의 수 $N$이 주어진다. ($ 2 \le N \le 300,000円 $)

둘째 줄부터 $N-1$개 줄에 걸쳐 트리 $A$에서 간선으로 연결된 두 정점의 번호가 공백을 기준으로 구분되어 주어진다.

출력

첫째 줄에 트리 $A$와 XOR 연산한 결과가 트리가 되는 트리 $B$가 존재한다면 YES, 존재하지 않는다면 NO를 출력한다.

가능한 트리 $B$가 존재한다면 간선으로 연결된 두 정점의 번호를 공백을 기준으로 구분하여 둘째 줄부터 $N-1$개 줄에 걸쳐 출력한다.

제한

힌트