13246 - Youbike Racing Tournaments   

Description

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:

  1. Divide special nodes into groups, for number of each is 2.
  2. For each group, pick one node that lies in the path of the two nodes of the group. The picked node can also choose the start point and end point of the path.
  3. The picked node of different groups can be the same.
  4. We want the number of picked nodes as small as possible.

We grantee that:

  1. There's only and exactly one path from any node to any other node .

For example:

samples

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.

 

Input

The first line contains an integer , there are testcases below.

For each testcase:

  1. The first line contains two integers and .
  2. Then lines below, each line contains two integers and , indicates there's a path from node to node (and node to node ).
  3. The last line contains integers, indicate the special nodes.

, , .

Output

For each testcase, output:

  1. First line contains the total number of picked nodes.
  2. Second line output the indices of the picked nodes.
  3. Then lines below. Each line contains three integers, which is two special nodes that divided to the same group and their picked node respectively, separated by a space.

If there are multiple answers (i.e. same total number of picked nodes but with different node indices), you may output any of them.

Sample Input  Download

Sample Output  Download

Tags




Discuss