압수르디스탄의 도로 3

압수르디스탄 사람들은 작년에야 도로 놓는 법을 알아냈다. 그 뒤로 각 도시는 자기 도시와 다른 도시 하나를 잇는 도로를 하나씩 놓았다. 새로 놓인 도로는 양쪽 방향으로 모두 다닐 수 있다.

당신이 산 여행 안내서에는 새로 놓인 도로가 전부 표시된 지도가 실려 있다. 지도에는 도로만 그려져 있고, 어느 도시가 어느 도로를 놓았는지는 적혀 있지 않다. 역사에 관심이 많은 당신은 이 대응 관계를 알아내려고 한다.

도로 $n$개의 정보가 주어질 때, 각 도시가 도로를 정확히 하나씩 놓은 것이 되도록 도로를 도시에 배정하라. 그런 배정은 적어도 하나 존재한다.

첫째 줄에 도시의 수이자 도로의 수인 정수 $n$이 주어진다. ($2 \le n \le 100000$)

다음 $n$개 줄에는 도로 하나의 정보가 두 정수 $a$, $b$로 주어진다. 도시 $a$와 도시 $b$를 잇는 도로가 있다는 뜻이다. ($1 \le a, b \le n$, $a \ne b$)

같은 두 도시를 잇는 도로가 여러 개 있을 수도 있다.

$n$개 줄을 출력한다. $i$번째 줄에는 도시 $i$가 놓은 도로를 정수 두 개 $i$와 $b$로 출력한다. $b$는 그 도로의 반대쪽 끝 도시이다. 입력에 주어진 각 도로는 출력에 정확히 한 번씩 나타나야 한다.

배정이 여러 가지이면 수열 $b_1, b_2, \dots, b_n$이 사전순으로 가장 앞서는 배정 하나만 출력한다.