34532번 - Designing a Tree 스페셜 저지

문제

$N$개의 정점으로 이루어진 그래프가 주어진다. 각 정점은 1ドル$부터 $N$까지 순서대로 번호가 매겨져 있고, 초기에는 각 정점 사이에 간선이 없다.

이때, 각 $i(1≤i≤N-1)$번 정점에 대해 $L_i≤j_i≤R_i(1≤L_i≤R_i≤N)$인 $j_i$를 골라서 $i$번 정점과 $j_i$번 정점을 연결하는 무향 간선을 추가할 수 있다.

$j_i$를 적절히 골라서 그래프를 트리로 만드는 프로그램을 작성해 보자.

입력

첫째 줄에 $N$이 주어진다. $(2≤N≤500,円 000)$

둘째 줄부터 $N-1$개의 줄에 걸쳐 순서대로, 두 정수 $L_i,ドル $R_i$가 공백으로 구분되어 주어진다. $(1≤L_i≤R_i≤N)$

출력

그래프를 트리로 만들 수 없다면 첫째 줄에 NO를 출력한다.

그래프를 트리로 만들 수 있다면 첫째 줄에 YES를 출력한다. 둘째 줄에는 $N-1$개의 정수를 공백으로 구분해서 출력한다. $i$번째 정수는 $j_i$를 의미한다. 정답이 여러 개라면 그중 하나만 출력한다.

제한

노트

트리는 무방향 사이클이 없는 연결 그래프를 의미한다.