The world's largest youbike racing contest is holding...... again! It's time to learn to youbike again...
However, the judgements and organizers decide to change the rule of competition for the second season: intercity youbike racing contest - youbike racing tournaments!
The youbikers are divided into groups by their cities, each group stays in its own city. If two groups are going to compete, both of the groups have to move to the assigned venue city and compete each other.
For the first round, the organizers decide to hold a knockout stage. That is, two groups compete each other, and the lose one is eliminated.
You are one of the organizers, who is assigned to make decision of the complete groups and location of venue cities. Note that if the venue city of two knockout competition is held in the same city, the organizers will cost less, so the host wants the number of venue cities as small as possible.
Given a map with nodes, edges, and special nodes. You need to:
We grantee that:
For example:
The nodes with bold red frame are the special nodes, and the nodes filled with red are possible choices of picked node.
The minimum number of picked nodes are 1 for the three cases. For case 2, we can pick node 3 as our picked node, where node 3 lies in the path of (6,2) and (5,0), and so do node 4 and 1.
The first line contains an integer , there are testcases below.
For each testcase:
, , .
For each testcase, output:
If there are multiple answers (i.e. same total number of picked nodes but with different node indices), you may output any of them.