23043번 - 트리 찾기 인터랙티브

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

$N$개의 정점으로 이루어진 트리 $T$가 있다. 처음에 $T$의 간선들은 주어지지 않는다.

여러분은 $T$의 간선들을 모두 알아내야 한다. 이를 위해 채점 시스템에 다음의 질의를 할 수 있다.

• 자연수 $K$와 서로 다른 $K$개의 정점 $u_1$, $\cdots$, $u_K$를 선택한다. ($1 \le K \le N$)

이 질의에 대해 채점 시스템은 다음 조건을 만족하는 정점 $v$의 개수를 알려준다.

• $u_i$와 $u_j$를 잇는 최단 경로 위에 $v$가 있도록 하는 $i$, $j$($1 \le i \le j \le K$)가 존재한다.

질의를 $11\,111$회 이하로 사용해 모든 간선들을 알아내야 한다.

입력의 첫 줄에 $T$의 정점의 수 $N$이 주어진다. $(2 \le N \le 1\,000)$

이후 인터랙션이 시작된다.

$T$의 간선들을 알아내기 위해 채점 시스템에 다음과 같은 질의를 할 수 있다.

• 첫 줄에 $K$를 출력한다.
• 다음 줄에 $u_1$, $\cdots$, $u_K$를 공백으로 구분하여 출력한다.

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

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

각각의 질의 이후에는 채점 시스템이 질의에 대한 답을 줄 것이다. 표준 입력으로 정수 하나를 입력받아 질의의 답을 얻을 수 있다.

단, 질의를 $11\,112$회 이상 사용했거나 잘못된 형식의 질의를 했다면 틀렸습니다를 받는다. 프로그램을 즉시 종료하지 않을 경우 다른 결과를 받을 수 있음에 유의하라.

모든 간선들을 알아냈다면 이를 출력하고 프로그램을 종료해야 한다. 간선들을 출력하는 방법은 다음과 같다.

• 첫째 줄에 !를 출력한다.
• 다음 $(N-1)$개의 줄에 걸쳐 각 간선이 잇는 두 정점의 번호를 공백으로 구분하여 출력한다.

$T$의 모든 간선들을 정확히 구했다면 맞았습니다를 받는다. 그렇지 않다면 틀렸습니다를 받는다.