시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 1024 MB 67 25 23 39.655%

문제

승현이는 오랜만에 휴가를 얻어 오랜 꿈이었던 전국일주를 할 계획을 세웠다.

승현이가 살고 있는 나라는 1번부터 N번까지의 N개 마을과 서로 다른 두 마을간을 잇는 N(N-1)/2개의 도로로 이루어져 있다. 승현이는 각 마을을 정확히 한 번씩 지나 여행을 시작한 마을로 돌아오려고 한다. 문제는 도로 종류가 자갈 도로, 진흙 도로의 두 가지라는 점이다.

자갈 도로와 진흙 도로를 지나갈 수 있는 타이어는 서로 다르다. 따라서 승현이는 지나는 도로의 종류가 바뀔 때마다 타이어를 갈아 주어야 한다. 승현이는 타이어를 딱 한 번 바꿀 수 있을 만큼 여유가 있기 때문에, 여행을 하는 도중 도로 종류가 최대 한 번만 바뀌는 여행 경로를 찾고자 한다.

승현이는 현재 마을들을 잇는 도로가 어떤 종류인지 전혀 모르고 있다. 승현이는 디지털 문명과는 담을 쌓고 사는 사람이기 때문에, 친구인 제연이에게 도로의 종류에 대해 물어보고자 한다. 승현이는 한 번의 질문으로 두 마을을 잇는 도로의 종류를 알아낼 수 있다. 하지만 2N번의 질문 후에는 제연이의 인내심이 바닥나 더 이상 질문을 할 수 없다.

다행히도, 각 도로의 종류를 어떻게 정하든 간에 2N(N-1)/2가지의 모든 경우에 대해서 승현이의 조건을 만족하는 여행 경로가 존재함이 보장된다고 한다. 하지만 승현이는 어떤 질문을 해야 할지 결정하지 못해 당신에게 도움을 청했다. 승현이가 무사히 전국일주를 할 수 있도록 효율적으로 질문을 던져 조건을 만족하는 여행경로를 찾아 주자.

중요: 채점 시스템은 맨 처음에 각 도로의 종류를 정해놓지 않고, 여러분의 질문에 따라 도로의 종류를 결정할 수 있다. 단, 이전까지의 답변들과 모순되는 답변은 하지 않는다.

상호 작용

입력의 첫 줄에 마을의 수 N이 주어진다.

그 뒤로는 여러분의 프로그램과 채점 시스템이 interaction하면서 진행된다.

i번 마을과 j번 마을을 잇는 도로의 종류는 ? i j을 표준 출력 스트림(stdout)으로 출력하여 물어볼 수 있다. (1 ≤ i, jN, ij) 출력한 후에는 표준 출력 버퍼를 flush해 주어야 한다. 언어별로 표준 출력 버퍼를 flush하는 방법은 다음과 같다.

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

각각의 질문 이후에는 채점 시스템이 질문에 대한 답을 줄 것이다. Gravel은 자갈 도로, Mud는 진흙 도로를 뜻한다. 이러한 질문은 최대 2N번까지만 할 수 있다.

조건을 만족하는 경로를 찾은 경우, 순서대로 a1번 마을, a2번 마을, …, an번 마을을 차례로 지나 다시 a1번 마을로 돌아오는 경로가 조건을 만족한다고 하면 ! a1 a2an의 형태로 답을 출력하고 프로그램을 종료해야 한다.

채점 프로그램은 현재까지 알려진 정보와 모순되지 않는 모든 경우의 도로망에서 참가자가 제시한 경로가 조건을 만족할 때 이를 정답으로 처리한다. 현재까지 알려진 정보와 모순되지 않으면서 참가자가 제시한 경로가 두 번 이상 도로 종류가 바뀌도록 도로들의 종류를 설정할 수 있다면 채점 프로그램은 이를 오답으로 처리한다.

제한

  • 3 ≤ N ≤ 2,000

예제 입력 1

4

Mud

Gravel

Gravel

예제 출력 1


? 1 2

? 2 3

? 3 4

! 2 3 4 1

입출력 예제는 채점 프로그램과의 상호 작용 방식을 보여주기 위한 것으로, 실제 채점 프로그램과의 작동 방식과는 다를 수 있다.

채점

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