P8004 Welcome to Lunatic City

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.)

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$.

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$.

### 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.** | Subtask ID | Score | Special Constraints | | :----------: | :----------: | :----------: | | $0$ | $15$ | $n\le 9$，$L=100$ | | $1$ | $10$ | $m=n-1$，$L=5n$ | | $2$ | $20$ | $n\le 70$ and there are at most five test cases with $n>30$, $L=n^2$ | | $3$ | $20$ | $n\le 1000$ and there are at most five test cases with $n>100$, $L=100n$ | | $4$ | $30$ | $L=5n$ | | $5$ | $5$ | $L=n$ | 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