전선 퍼즐

이 문제는 대화형 문제입니다. 여러분의 프로그램은 표준 입력과 표준 출력을 통해 채점 프로그램과 상호작용합니다.

친구들이 다음과 같은 구조의 퍼즐을 만들었습니다. 불투명한 파이프에 서로 비슷한 전선 $n$개가 통과합니다. 파이프의 한쪽 끝은 왼쪽 끝, 다른 쪽 끝은 오른쪽 끝입니다. 양쪽 끝에는 전선 $n$개가 보이며, 각 전선은 1부터 $n$까지 서로 다른 정수로 표시되어 있습니다. 다만 같은 전선이라도 두 끝에서 서로 다른 번호가 붙을 수 있습니다.

이 퍼즐의 목표는 전선 양 끝의 대응 관계를 찾는 것입니다. 1부터 $n$까지의 각 $i$에 대해, 오른쪽 끝에서 번호가 $i$인 전선이 왼쪽 끝에서 번호 $a_i$를 가진다고 할 때 $a_i$를 구하세요.

다음과 같이 질의할 수 있습니다. 정수 $k$ ($1 \le k \le n$)를 선택하고, 오른쪽 끝의 전선을 공집합이 아닌 $k$개의 그룹으로 나눕니다. 같은 그룹에 속한 전선은 모두 연결됩니다. 그 뒤 특수 장치를 사용하면 왼쪽 끝의 전선 쌍마다 오른쪽 끝에서 두 전선이 연결되어 있는지 알 수 있습니다. 따라서 왼쪽 끝 번호들 중 같은 그룹에 속한 번호가 무엇인지 알 수 있습니다.

정확히 세 번의 질의로 대응 관계를 찾으세요.

동작 방식을 이해하려면 아래 힌트의 예시를 참고하세요.

위의 예시를 살펴봅시다.

전선은 4개입니다.

첫 번째 질의는 3개의 그룹으로 나눕니다. 오른쪽 번호 1과 2의 전선은 연결하고, 3과 4의 전선은 각각 혼자 그룹을 이룹니다.

채점 프로그램은 왼쪽 번호 2와 3의 전선이 같은 그룹이고, 왼쪽 번호 1과 4의 전선은 각각 혼자 그룹이라고 응답합니다.

이 응답으로부터 왼쪽 번호 2와 3의 전선은 오른쪽 번호 1과 4의 전선 중 어느 쪽과 대응하는지 순서만 알 수 있고, 왼쪽 번호 1과 4의 전선은 오른쪽 번호 3과 4의 전선과 순서만 알 수 있습니다.

두 번째 질의는 2개의 그룹으로 나눕니다. 오른쪽 번호 1, 2, 3의 전선은 연결하고, 번호 4의 전선은 혼자 둡니다.

채점 프로그램은 왼쪽 번호 2, 3, 4의 전선의 오른쪽 끝이 연결되어 있다고 응답합니다.

오른쪽 번호 4의 전선은 왼쪽 번호 1을 가지므로, 오른쪽 번호 3의 전선은 왼쪽 번호 4를 가집니다.

세 번째 질의로 오른쪽 번호 1과 2의 전선을 구분합니다. 이제 대응 관계가 모두 정해집니다.