Problem Description

Country M consists of $n$ cities and $n-1$ bidirectional high-speed railways. The $n$ cities can reach each other through the railways.

Because Country M has the most advanced technology, in order to speed up transportation, it can place some paired portals on the railways, with the total number of pairs not exceeding $L$. When a train runs on a railway, whenever it encounters a portal, it will be teleported. Each portal has a front side and a back side: if the train enters from the front side, it will exit from the front side of the portal paired with it; if it enters from the back side, it will exit from the back side. A portal can be placed anywhere in the middle of a railway. (If anything in this description is unclear, please refer to the sample explanation.)

Also, since Country M has extremely fast trains, travel time is only spent on stops. Therefore, the distance from city $i$ to city $j$, $dis(i,j)$, is defined as the number of cities the train passes through (including the destination but excluding the start).

Now Country M has designated $m$ important cities $x_1,x_2,\dots,x_m$. Please place at most $L$ pairs of portals in a proper way so that the sum of distances from the capital city $1$ to these cities is minimized, i.e., minimize $\sum_{i=1}^m dis(1,x_i)$, and output a construction. Meanwhile, the placed portals must ensure that all cities are still mutually reachable.

(Due to some properties of the special judge, please do not place more than $L$ portals on a single railway, otherwise you will be judged WA.)

Input Format

The first line contains an integer $T$, the number of test cases.

For each test case:

The first line contains three integers $n$, $m$, and $L$, representing the number of cities, the length of $x$, and the maximum number of portal pairs that can be placed.

The next $n-1$ lines: the $i$-th line contains two positive integers $u_i, v_i$, indicating that the $i$-th railway connects these two cities.

The next line contains $m$ integers representing $x$.

Output Format

For each test case:

The first line contains one integer, the minimum sum of distances.

The next $n-1$ lines: the $i$-th line starts with an integer $num$, the number of portals on the $i$-th railway. Then follow $num$ pairs of integers $x, f$, describing in order the portal id and its orientation on the direction from $u_i$ to $v_i$. Here $f=0$ means the front side faces city $u_i$, and $f=1$ means the front side faces city $v_i$.

Portal ids are $1\sim \frac{\sum num}{2}$, and each id must appear exactly twice.

For each test case, the total number of portal pairs must not exceed $L$, i.e., $\frac{\sum num}{2}\le L$.

2
4 3 100
1 2
2 3
3 4
2 3 4
5 2 100
1 2
2 3
3 4
3 5
4 5

6
0
0
0
5
1 1 0
3 4 0 3 1 1 1
1 2 0
3 2 1 3 0 4 1

Hint

Sample Explanation

For the second test case in the sample, the shape of the tree and the portal placement are as follows:

The red portals have id $1$, the green ones have id $2$, the blue ones have id $3$, and the purple ones have id $4$. The arrows indicate the direction that the front side of each portal faces. The bold nodes are important cities.

The shortest path from city $1$ to city $5$ is as follows:

First, starting from city $1$, enter the front side of the red portal and arrive at city $3$.

Then start from city $3$, enter from the front side of the green portal, arrive at a segment of railway between the green and blue portals on the road $3-5$, then enter the front side of the blue portal, arrive at a segment of railway between the blue and red portals on the road $2-3$, then enter the back side of the red portal, and finally arrive at city $2$.

Finally, enter from the front side of the purple portal and arrive at city $5$. Along the way, excluding city $1$, it passes through cities $3, 2, 5$, so under this portal placement $dis(1,5)=3$.

Also $dis(1,4)=2$. It can be proven that there is no placement that makes $dis(1,4)+dis(1,5)$ smaller.

Constraints

This problem uses bundled testdata.

For all testdata, it is guaranteed that $1\le T\le 100$, $1\le n\le 10^5$, $1\le \sum n\le 5\times 10^5$, $0\le m<n$, $2\le x_i\le n$, and all $x_i$ are distinct.

Translated by ChatGPT 5