시간 제한메모리 제한제출정답맞은 사람정답 비율
2.5 초 1024 MB2113685.714%

문제

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

고슴도치 귀엽지 않나요?

귀여운 고슴도치!

키파는 "성게 그래프"도 있는데 이렇게 귀여운 고슴도치에 대응하는 그래프가 없는 것은 아무래도 말이 안 된다고 생각해서, 고슴도치 그래프를 만들기로 했습니다.

고슴도치 그래프는 다음과 같은 두 가지 성질을 만족하는 방향 없는 연결 그래프입니다. 이 그래프에는 self-loop(한 정점 $v$와 같은 정점인 $v$를 연결하는 간선)와 multiedge(서로 다른 두 정점 $v$와 $w$에 대해 $v$와 $w$를 연결하는 서로 다른 간선 $e_{1}$과 $e_{2}$)가 없습니다.

  • 사이클이 정확히 하나 존재합니다. 이 사이클을 고슴도치의 몸통이라고 부르겠습니다. 몸통의 크기는 사이클에 속한 정점의 개수입니다. 사이클이 항상 존재하기 때문에 몸통의 크기는 항상 $3$ 이상이라는 점에 유의하세요.
  • 사이클에 속하지 않은 정점의 차수가 $1$입니다.

키파는 고슴도치 그래프를 열심히 키운 결과 각 그래프가 $V = 10^{6}$개의 정점으로 이루어진 고슴도치 그래프를 총 $N$개 가지게 되었습니다. 키파는 각 고슴도치 그래프를 다음과 같은 방법으로 어루만져 주기로 했습니다.

  1. 각 노드에 붙어 있는 간선의 방향을 한 방향으로 정하되, 모든 노드가 나가는 방향의 간선을 정확히 하나 가지도록 정합니다. 임의의 고슴도치 그래프에 대해, 간선의 방향을 위 조건을 만족하도록 정하는 것이 항상 가능함을 증명할 수 있습니다.
  2. 다음을 최대 $M = 1\,204$번 반복합니다.
    1. 정점 $v$와 $\left\lfloor10^{12.4}\right\rfloor = 2\,511\,886\,431\,509$ 이하의 아무 양의 정수 $x$를 고릅니다.
    2. $v$에서 화살표를 $x$번 따라가며 고슴도치 그래프를 쓰다듬습니다. 모든 노드가 나가는 방향의 간선이 하나 있기 때문에 도착 노드는 하나로 정해지며, 이 도착 노드가 어디인지 알 수 있습니다.

과정 1은 키파가 이미 임의로 방향을 정했습니다.

키파는 고슴도치 그래프를 어루만져 주는 것뿐만 아니라 각 고슴도치 그래프의 몸통의 크기를 알고 싶어했습니다. 하지만 키파는 이걸 생각하기에는 머리가 너무 아팠기 때문에, 과정 2를 여러분에게 맡기기로 했습니다.

여러분은 각 고슴도치 그래프에 대해 과정 2를 시행한 후 얻은 정보로 각 고슴도치의 몸통의 크기를 알아내야 합니다.

입력

첫째 줄에 $10$ 이하의 양의 정수 $N$이 주어집니다. 그러고 나면 인터랙션이 시작됩니다.

인터랙션

여러분은 채점 시스템에게 다음과 같은 질의를 할 수 있습니다.

  • ? v x: 정점 $v$에서 화살표를 $x$번 따라가서 도착한 노드 번호를 돌려줍니다. $1 \leq v \leq V$, $1 \leq x \leq \left\lfloor 10^{12.4}\right\rfloor = 2\,511\,886\,431\,509$를 만족해야 합니다. 이 질의는 그래프 당 최대 $M$번 할 수 있으며, 결과는 도착 정점 번호를 나타내는 $1$ 이상 $V$ 이하의 정수입니다.
  • ! s: 현재 어루만지고 있는 그래프의 몸통의 크기 $s$를 채점 프로그램에게 알려주는 질의입니다. 그래프 당 한 번 질의할 수 있으며, 결과는 몸통의 크기가 맞았음을 의미하는 $1$이거나 몸통의 크기가 틀렸음을 의미하는 $-1$입니다. 크기가 맞은 경우 다음 그래프로 넘어갑니다.

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

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

어떤 질의에서든지 음수를 응답으로 받았을 경우 프로그램을 즉시 정상 종료해야 하며, 이 경우 틀렸습니다를 받습니다. 프로그램을 즉시 종료하지 않을 경우 다른 결과를 받을 수 있음에 주의하세요.

$N$개의 ! 질의에서 모두 $1$을 받은 경우 프로그램을 종료하면 그 테스트 케이스에 대해서는 맞은 것으로 처리됩니다.

예제 입력 1

1

3

7

10

1

예제 출력 1

? 1 2

? 2 5

? 10 11

! 11

출처

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

채점 및 기타 정보

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