강 건너기

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

강 위에 통나무가 떠다니고 있다. 각 통나무는 시작 지점과 끝 지점을 가지며, 모든 통나무의 시작 지점과 끝 지점은 다른 통나무의 시작 지점이나 끝 지점과 모두 서로 다르다. 즉, $i$번째 통나무의 시작 지점이 $s_i$, 끝 지점이 $e_i$이고 $j$번째 통나무의 시작 지점이 $s_j$, 끝 지점이 $e_j$일 때, $i \neq j$이면 $s_i \neq s_j$, $s_i \neq e_j$, $e_i \neq s_j$, $e_i \neq 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()