서울과학고대유적 탐험하기 2

서울과학고대유적 탐험하기 1, 2 문제는 질문의 유형을 제외한 모든 사항이 동일합니다.

이 문제는 인터랙티브 문제입니다.

최근 고고학자들은 "서울과학고대유적"이라는 고대 유적을 발견하였다!

서울과학고대유적은 $1$번부터 $N$번까지 $N$개의 유적들과 서로 다른 두 유적을 연결하는 $N-1$개의 도로로 연결된 트리 형태로 표현할 수 있다. 모든 도로는 양방향으로 이동할 수 있고, 도로를 이용해 모든 유적 사이를 이동할 수 있다.

서울과학고대유적의 도로들은 세월이 지나면서 사라진 지 오래지만, 도로에 대한 정보를 얻을 수 있는 탐험록이 전해져 내려오고 있다. 탐험록은 $N$개의 탐험 기록으로 이루어져 있고, 각 탐험 기록은 $N$개의 유적들을 특정한 순서로 방문한 기록이다.

고고학자들이 서울과학고대유적 탐험록을 분석한 결과, $i$번째 탐험 기록은 다음과 같은 방법으로 유적들을 방문한 결과임을 밝혀냈다.

• 탐험은 $i$번 유적에서 시작한다. 즉, $i$번째 탐험 기록에는 $i$번 유적이 첫 번째로 기록되어 있다.
• 현재 위치한 유적과 도로로 직접 연결된 유적 중 아직 방문하지 않은 유적이 존재한다면, 그들 중 번호가 가장 작은 유적을 방문하고 탐험록에 기록한다.
• 만약 도로로 직접 연결된 유적들이 모두 방문되었다면, 도로로 직접 연결된 유적 중 $i$번 유적과 가장 가까운 유적으로 이동한다. 이 경우 현재 유적이 $i$번 유적이 아님을 증명할 수 있다.
• 모든 유적을 방문하였을 때 탐험을 종료한다.

단, 위의 방법으로 탐험을 진행하였을 때 시작점에 관계 없이 모든 유적을 방문하고 탐험록에 기록함을 증명할 수 있다.

서울과학고대유적의 구조를 알아내기 위해 당신은 다음과 같은 질문을 할 수 있다:

• ? i j: $i$번 탐험 기록에 기록된 유적의 순서 중 $j$번 유적이 몇 번째로 기록되었는지를 질문한다.

이때, 서울과학고대유적의 구조를 알아내는 프로그램을 작성하자.

• $2 \le N \le 10^3$

출력 버퍼를 비우는 방법은 다음과 같다.

• C: fflush(stdout)
• C++: std::cout << std::flush
• Java: System.out.flush()
• Python: sys.stdout.flush()

이외의 언어에 대해서는 언어별 명세를 참고해야 한다.