시간 제한메모리 제한제출정답맞은 사람정답 비율
5 초 1024 MB40141338.235%

문제

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

$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$의 모든 간선들을 정확히 구했다면 맞았습니다를 받는다. 그렇지 않다면 틀렸습니다를 받는다.

예제 입력 1

5


3


5


2


4


3





예제 출력 1


2
4 5

3
5 3 4

2
1 2

3
5 4 1

3
2 4 5

!
3 1
2 4
2 1
5 2

출처

University > 서울대학교 > 2021 서울대학교 프로그래밍 경시대회 - Division 2 H번

채점 및 기타 정보

  • 예제는 채점하지 않는다.