Vault Heist 2

This is a two-step problem. In each test case, the program runs exactly twice. See the grading section for details.

Yeongu and Jeonghu are safecrackers who make money by robbing bank vaults. Today they plan to rob $T$ bank vaults. To rob one vault, Jeonghu first breaks into the bank system and finds the vault's password, an integer no greater than $10^{18}$. He then sends it to Yeongu through TTS (Tree Transmission System). If Yeongu recovers the correct password for every bank and opens every vault safely, both of them celebrate with a bonus party. Otherwise, the bank's security system arrests them.

Before the operation, the two met in secret and agreed on the following.

• Before Yeongu enters a bank, he and Jeonghu agree on a rule for passing the password. They both know the password is an integer no greater than $10^{18}$.
• Yeongu enters the bank, and Jeonghu breaks into the bank system to find the password. Following the agreed rule, Jeonghu builds a tree to send through TTS. The tree must satisfy the conditions below. Then he sends the number of vertices and the edge list to TTS.
  • The tree has between $1$ and $100$ vertices. If the tree has $N$ vertices, its vertices are the positive integers from $1$ to $N$.
  • No vertex has four or more incident edges.
• TTS has a critical bug: when it transmits a tree, at most one edge can be removed. The tree then splits into one or more connected components. TTS picks one of the largest components arbitrarily and discards the rest. If the remaining component has $N'$ vertices, TTS renumbers its vertices $1, 2, \cdots N'$.
• TTS sends $N'$ and the edge list to Yeongu. TTS chooses the order of the edges arbitrarily.
• Using the information from TTS and the rule agreed on earlier, Yeongu recovers the password. If it matches the password Jeonghu found, Yeongu opens the vault safely.

Play the roles of Yeongu and Jeonghu, open the vaults safely, and enjoy the bonus party.

• $1 \le T \le 1000$
• Every number in the input is an integer.