크리스마스 시즌입니다! 대부분의 직장이 비밀 산타 선물 교환을 준비하는 동안, 여러분의 직장에서는 더 사악한 음모, 즉 산타의 비밀을 파헤치려는 계획을 세우고 있습니다.

산타는 지구상의 모든 사람에 대한 '착한 아이/나쁜 아이' 명단을 가지고 있습니다. 이 명단은 내용이 매우 민감하기 때문에, $N$개의 문자로 이루어진 난해한 언어인 '노스 폴란드어(North-Polish)'로 작성되어 있습니다. 보안을 강화하기 위해 산타는 이 명단을 치환 암호(substitution cipher)로 암호화했습니다. 이는 $1, 2, \dots, N$의 순열 $H$를 사용하여 각 노스 폴란드어 문자 $i$를 서로 다른 문자 $H(i)$로 매핑하는 방식입니다. 이러한 암호에서는 두 문자가 동일한 대상 문자로 매핑되지 않습니다. 즉, 형식적으로 $i \neq j$이면 $H(i) \neq H(j)$입니다. 그렇지 않으면 산타가 자신의 명단을 해독할 수 없기 때문입니다! (산타는 더 까다롭게 만들기 위해 일부 문자를 자기 자신에게 매핑할 수도 있습니다, 즉 $H(i) = i$.)

다행히도 산타의 서버는 보안이 허술하게 설계되어 공용 인터넷에 노출되어 있습니다. 여러분과 동료들은 산타의 서버를 해킹하여 명단을 해독하고, 여러분 모두가 '나쁜 아이'임을 확인하고자 합니다! (해커는 항상 나쁜 아이니까요.)

이 서버는 산타가 이동 중에도 빠르게 명단을 확인할 수 있도록 만들어졌습니다. 사용자가 서버에 연결하면, 서버는 순열 $H$를 인코딩하는 $N$개의 정수 $H(1), H(2), \dots, H(N)$을 입력하라는 메시지를 표시하고, 이 목록이 올바른지 확인한 다음 산타의 비밀 명단을 해독합니다. 수개월의 연구 끝에 여러분은 부채널 타이밍 취약점을 발견했습니다. 순열 $Q$를 입력한다고 가정해 봅시다. 만약 $H = Q$라면, 서버는 즉시 접근을 허용합니다. 그렇지 않은 경우, $N$개의 정점으로 구성된 그래프를 고려하고 각 정점 $i$에서 정점 $H(Q(i))$로 향하는 간선을 추가합니다. 여러분은 서버의 복잡한 인증 알고리즘이 응답으로 'Access Denied(접근 거부)' 오류 메시지를 보내는 데 걸리는 시간이 결과 그래프의 연결 요소(connected component) 개수와 정확히 일치한다는 사실을 발견했습니다.

예를 들어, $N = 4$이고 암호 순열 $H$가 다음과 같다고 가정해 봅시다:

만약 입력값 4 3 2 1로 서버에 로그인을 시도하면, 이 순열은 $H$와 일치하지 않으며 위에서 설명한 그래프는 두 개의 연결 요소(간선 $1 \to 4 \to 2 \to 1$로 이루어진 사이클 하나와 자기 루프 $3 \to 3$으로 이루어진 요소 하나)를 가지므로, 서버는 2초의 지연 시간 후에 'Access Denied' 오류 메시지로 응답할 것입니다.

서로 다른 입력 $Q$를 사용하여 서버에 여러 번 로그인을 시도하더라도, 서버는 매번 동일하게 저장된 $H$를 기준으로 $Q$를 인증한다는 점에 유의하세요. 입력에 따라 $H$가 변경되지는 않습니다.

산타는 자신의 서버에 무단 요청이 쏟아지면 이를 알아챌 것입니다. 여러분은 너무 많은 의심을 사지 않고 최대 1,510번의 로그인 시도만 할 수 있다고 추정했습니다. 암호 순열을 결정하기 위한 효율적인 전략을 찾을 수 있을까요?

인터랙션

이 문제는 인터랙티브 문제입니다. 인터랙션은 표준 입력에서 노스 폴란드어의 문자 수인 정수 $N$ ($1 \le N \le 220$)을 읽는 것으로 시작합니다. 심판(judge)은 적응형(adaptive)이 아닙니다. 숨겨진 순열 $H$는 이 시점에 결정되며 인터랙션이 끝날 때까지 변경되지 않습니다.

서버에 로그인을 시도하려면, $Q$가 $\{1, 2, \dots, N\}$의 순열일 때 $N$개의 공백으로 구분된 정수 $Q(1), \dots, Q(N)$을 한 줄에 출력하세요. 그런 다음 표준 입력에서 서버가 여러분의 입력에 응답하는 데 걸린 시간(초)을 나타내는 정수 하나를 읽으세요.

이 지연 시간이 0이면, 암호 순열 $H$를 성공적으로 찾은 것이며 프로그램은 종료되어야 합니다. 그렇지 않다면, 이 지연 시간은 위에서 설명한 절차에 따라 구축된 그래프의 연결 요소 개수입니다.

최대 1,510번까지 로그인을 시도할 수 있습니다. 시도 횟수를 모두 소진하면 프로그램은 깔끔하게 종료되어야 합니다(단, 산타의 명단을 해독하지 못한 것으로 간주되어 오답 처리됩니다).

참고

• 출력하는 각 줄 뒤에는 반드시 출력 스트림을 플러시(flush)하고, 인터랙션이 완료된 후에는 깔끔하게 종료하는 것을 잊지 마세요. 또한 어떤 정보를 어떤 출력 줄에 인쇄해야 하는지에 대한 인터랙션 프로토콜을 정확히 따르도록 하세요. 예를 들어, 프로토콜이 한 줄에 공백으로 구분된 정수 목록을 인쇄하도록 요구하는 경우, 심판은 각 정수를 별도의 줄에 인쇄하는 것을 허용하지 않습니다.
• 심판이 유효하지 않거나 예상치 못한 입력을 받으면 -1을 출력하고 즉시 종료합니다. 여러분의 프로그램은 이를 감지하고 깔끔하게 종료하여 'Wrong Answer' 판정을 받아야 합니다. 프로그램이 심판의 추가 인터랙션을 기다리며 차단되거나, -1을 연결 요소의 개수로 해석하려고 시도하면 'Wrong Answer' 대신 'Time Limit Exceeded' 또는 'Runtime Error'와 같은 다른 거부 판정을 받을 수 있습니다.
• 로컬 테스트를 위한 명령줄 도구가 제공되었습니다. 이 도구의 상단에는 사용법을 설명하는 주석이 포함되어 있습니다.

예제

예제 1

3

1 2 3

1

2 1 3

2

3 1 2

0