31033번 - 금고 털이 2 투 스텝

문제

이 문제는 투 스텝 문제로, 각 테스트 케이스마다 프로그램이 총 두 번 실행된다. 이에 대한 자세한 정보는 채점 방법 문단을 참조하라.

영우와 정후는 은행의 금고를 털어 돈을 버는 금고 털이이다. 오늘은 총 $T$ 개의 은행의 금고를 털려고 한다. 한 금고를 털 때에는 먼저 정후가 은행 시스템에 침입해 10ドル^{18}$ 이하의 정수인 금고의 비밀번호를 알아내고, 이것을 TTS(Tree Transmission System)를 이용하여 영우에게 전달한다. 영우가 모든 은행의 올바른 비밀번호를 알아내고 금고를 무사히 턴다면 두 사람은 행복하게 성과급 파티를 즐기고, 그렇지 않다면 은행의 엄격한 보안 시스템에 의해 체포되어 철창 신세가 된다. 이렇게 중요한 작전을 실행에 옮기기 전, 두 사람은 비밀리에 다음과 같은 작전 회의를 했다.

• 영우가 은행에 진입하기 전에, 정후와 상의하여 비밀번호를 전달할 규칙을 정한다. 두 사람은 비밀번호가 10ドル^{18}$ 이하의 정수라는 사실을 알고 있다.
• 영우가 은행에 진입하고, 정후가 은행 시스템에 침입하여 금고의 비밀번호를 알아낸다. 정후는 영우와 사전에 정한 규칙에 따라 TTS에 전달할 트리를 만든다. 이때 트리는 다음의 조건에 맞게 만든 후 TTS에 정점의 개수와 간선의 목록을 전달한다.
  • 트리의 정점의 수는 1ドル$과 100ドル$ 사이의 정수이고, 트리의 크기가 $N$일 때 트리의 정점은 1ドル$부터 $N$ 이하의 양의 정수이다.
  • 간선이 네 개 이상 연결된 정점이 없다.
• 그런데 TTS에는 치명적인 버그가 있어서, 트리를 전달할 때 최대 하나의 간선이 제거될 수 있다. 이렇게 되면 트리는 하나 이상의 연결 요소(connected component)로 분리되는데, TTS는 그중 크기가 가장 큰 것 중 하나를 임의로 고르고 나머지 연결 요소들은 제거한다. 남은 연결 요소의 정점 수를 $N'$이라 할 때, TTS는 고른 연결 요소의 정점의 번호를 1,ドル 2, \cdots N'$으로 다시 배정한다.
• TTS는 $N'$과 간선의 목록을 영우에게 전달한다. 이때 전달하는 간선의 순서는 TTS가 임의로 정한다.
• 영우는 TTS로부터 전달받은 정보와 처음 정후와 상의한 규칙을 바탕으로 금고의 비밀번호를 알아낸다. 그 비밀번호가 처음 정후가 알아낸 비밀번호와 일치한다면 영우는 무사히 금고를 털 수 있다.

영우와 정후의 역할을 수행하여, 무사히 금고를 털고 성과급 파티를 즐기자.

채점 방법

하나의 테스트 케이스에 대하여 당신의 프로그램은 총 두 번 실행된다. 첫 번째 실행에서, 당신의 프로그램은 정후의 역할을 수행해야 한다. 두 번째 실행에서, 당신의 프로그램은 영우의 역할을 수행해야 한다. 두 번째 실행의 입력은 첫 번째 실행에서 당신의 프로그램이 출력한 결과를 바탕으로 만들어진다.

매 출력마다 출력 버퍼를 비울 필요는 없다.

첫 번째 실행

첫 번째 실행은 정후의 역할을 수행한다.

• 첫 번째 줄에 0이 주어진다. 이는 당신의 프로그램에게 첫 번째 실행임을 알리기 위한 것이다.
• 두 번째 줄에는 털 은행의 수 $T$가 주어진다.
• 세 번째 줄부터 $T$개의 줄에 걸쳐 각 은행 금고의 비밀번호가 주어진다. 비밀번호는 1 이상 10ドル^{18}$ 이하의 정수이다.

총 $T$개의 트리를 다음과 같은 형식으로 출력한다. $i$번째로 출력해야 하는 트리는 $i$번째로 입력된 비밀번호를 통해 생성된 트리여야 한다.

• 첫 번째 줄은 트리에 포함된 정점의 개수 $N$을 출력한다. $N$은 1ドル$ 이상 100ドル$ 이하의 정수이다.
• 두 번째 줄부터 $N-1$개의 줄에 걸쳐 트리의 각 간선이 연결하는 두 정점의 번호를 공백을 사이에 두고 출력한다.

두 번째 실행

두 번째 실행은 영우의 역할을 수행한다.

• 첫 번째 줄에 1이 주어진다. 이는 당신의 프로그램에게 두 번째 실행임을 알리기 위한 것이다.
• 두 번째 줄에는 은행의 수 $T$가 주어진다.
• 세 번째 줄부터 총 $T$개의 트리가 주어진다. 트리가 주어지는 형식은 첫 번째 실행에서 트리를 출력한 형식과 동일하다.

총 $T$개의 비밀번호를 $T$개의 줄에 걸쳐 출력한다. $i$번째 줄에 출력하는 비밀번호는 첫 번째 실행에서 $i$번째로 입력된 비밀번호와 같아야 한다.

입력

출력

제한

• 1ドル \le T \le 1000$
• 주어지는 모든 수는 정수이다.

힌트