전국일주

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

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

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

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

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

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

• 3 ≤ N ≤ 2,000