32989번 - 강 건너기 인터랙티브

문제

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

강 위에 통나무가 떠다니고 있다. 각 통나무는 시작 지점과 끝 지점을 가지며, 모든 통나무의 시작 지점과 끝 지점은 다른 통나무의 시작 지점이나 끝 지점과 모두 서로 다르다. 즉, $i$번째 통나무의 시작 지점이 $s_i,ドル 끝 지점이 $e_i$이고 $j$번째 통나무의 시작 지점이 $s_j,ドル 끝 지점이 $e_j$일 때, $i \neq j$이면 $s_i \ne s_j,ドル $s_i \ne e_j,ドル $e_i \ne s_j,ドル $e_i \ne e_j$이다.

또한, 각 통나무의 길이는 1ドル$ 이상 20ドル$ 이하이다. 다른 말로 통나무의 시작 지점이 $s,ドル 끝 지점이 $e$일때 1ドル \leq e - s \leq 20$이다. 이때 모든 통나무에 대해서 $s$와 $e$는 정수이다.

통나무를 이용하여 이 강을 건널 수 있다. $i$번째 통나무의 시작 지점이 $s_i,ドル 끝 지점이 $e_i$이고 $j$번째 통나무의 시작 지점이 $s_j,ドル 끝 지점이 $e_j$일 때, $s_i < s_j < e_i$이거나 $s_j < s_i < e_j$인 경우 $i$번째 통나무에서 $j$번째 통나무로 이동할 수 있다.

당신은 이 통나무들로 지도를 만들려고 한다. 자세히는, 한번에 바로 이동할 수 있는 두 통나무를 전부 찾으려고 한다. 하지만 안타깝게도 당신은 이 통나무들을 직접 볼 수 없다.

대신, 강이 있는 곳에 사는 현지인들의 도움을 받을 수 있다. 현지인들은 이 통나무를 통해서 자주 이동하기 때문에, 임의의 두 통나무에 대해서 한 통나무에서 다른 통나무로 이동해야 하는 최소 이동 횟수를 알고 있다.

당신은 아직 현지인들의 언어를 완벽하게 알지 못해, 다음과 같은 질문밖에 할 수 없다:

• $x,ドル $y$: $x$번 통나무에서 $y$번 통나무로 이동하기 위한 최소 이동 횟수

또한, 임의의 두 통나무에 대해 한 통나무에서 다른 통나무로 이동하는 방법이 항상 존재한다는 사실을 알고 있다.

현지인들을 계속 붙잡고 있을 수 없어, 질문은 최대 30000ドル$번까지 할 수 있다. 이를 이용해서 지도를 완성하자.

입력

첫 번째 줄에 통나무의 개수 $N$이 주어진다. ($ 1 \leq N \leq 500$)

출력

당신은 채점 시스템에게 다음과 같은 질의를 할 수 있다.

• ? x y: $x$번 통나무에서 $y$번 통나무로 이동하기 위한 최소 이동 횟수를 반환한다. 각 질의는 1ドル \leq x \leq N,ドル 1ドル \leq y \leq N$을 만족해야 한다. 이 질의는 최대 30000ドル$번 할 수 있다. 질의가 범위 조건을 만족하지 않거나 질의 횟수 제한을 초과하는 경우 -1을 반환한다. 이 경우 프로그램을 즉시 종료해야 한다.
• ! m: 이 질의는 한 번만 할 수 있다. 한 번의 이동으로 이동할 수 있는 통나무 쌍의 개수가 $m$개임을 의미한다. 이후 그다음 줄부터 $m$개의 줄에 그러한 쌍의 두 통나무 번호를 한 줄에 하나씩 공백으로 구분하여 전부 출력하여라. 이 질의를 한 즉시 프로그램을 종료해야 한다.

-1을 반환받은 뒤나 두 번째 질의를 한 뒤 프로그램을 종료하지 않으면 정의되지 않은 채점 결과를 받을 수 있다.

제한

노트

질의를 출력한 후에는 표준 출력 버퍼를 flush해 주어야 한다. 언어별로 표준 출력 버퍼를 flush하는 방법은 다음과 같다.

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