금고 털이 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로부터 전달받은 정보와 처음 정후와 상의한 규칙을 바탕으로 금고의 비밀번호를 알아낸다. 그 비밀번호가 처음 정후가 알아낸 비밀번호와 일치한다면 영우는 무사히 금고를 털 수 있다.

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

금고 털이 2

문제

제한