전국일주

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

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

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

승현이는 지금 도로 종류를 전혀 모른다. 디지털 기기와는 담을 쌓고 사는 승현이는 친구 제연이에게 도로 종류를 물어보려 한다. 질문 한 번으로 두 마을을 잇는 도로의 종류를 알아낼 수 있다. 하지만 $2N$번 질문하고 나면 제연이의 인내심이 바닥나서 더 이상 질문할 수 없다.

다행히 각 도로의 종류를 어떻게 정하든, 가능한 $2^{N(N-1)/2}$가지 경우 모두에 대해 조건을 만족하는 여행 경로가 존재함이 보장된다. 승현이가 무사히 전국일주를 마칠 수 있도록, 질문을 효율적으로 던져 조건을 만족하는 여행 경로를 찾아 주자.

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

3 ≤ N ≤ 2,000