Tina wonders how strong the friendships of the CerealCodes team are. She has a tree of $$$n$$$ ($$$n$$$ is even) nodes, where each node represents one CerealCodes team member. A tree is an undirected connected graph with $$$n - 1$$$ edges.
She also knows of $$$\frac{n}{2}$$$ pairs of friends, where pair $$$i$$$ consists of nodes $$$a_i$$$ and $$$b_i$$$. Each node on the tree belongs to exactly one of these pairs.
For each edge on the tree, Tina wants to know, if that edge was removed from the tree, what would be the minimum $$$i$$$ (if it exists) such that $$$a_i$$$ and $$$b_i$$$ are disconnected?
Tina needs to solve $$$t$$$ ($$$1 \leq t \leq 10^4$$$) separate test cases.
Each test case begins with a line containing an even integer $$$n$$$ ($$$2 \leq n \leq 5\cdot10^5$$$), the number of nodes in the tree.
$$$n-1$$$ lines follow, where the $$$i$$$th of these lines is the $$$i$$$th edge of the tree, $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$). This means that there is an edge between nodes $$$u_i$$$ and $$$v_i$$$. These edges will form a tree.
Lastly, there are $$$\frac{n}{2}$$$ more lines, which are the pairs of friends. The $$$i$$$th of these lines contains two integers, $$$a_i$$$ and $$$b_i$$$. Each integer from $$$1 \dots n$$$ belongs to exactly one pair.
It is guaranteed that the sum of $$$n$$$ over all test cases won't exceed $$$5\cdot10^5$$$.
For each test case, print a line containing $$$n-1$$$ integers, where the $$$i$$$th integer is the minimum $$$i$$$ such that $$$a_i$$$ and $$$b_i$$$ are disconnected if the $$$i$$$th edge was removed. If no such pair exists, print $$$-1$$$.
261 21 34 25 22 61 42 53 641 23 24 32 31 4
1 3 1 2 3 2 1 2
The tree in the first test case Problem Credits: Timothy Gao
