금고 털이 2

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

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

작전을 실행하기 전, 두 사람은 비밀리에 다음과 같이 회의했다.

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

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

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