Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4112
Trees in the Pocket

Time Limit: 6 Seconds      Memory Limit: 262144 KB

DreamGrid has just found two trees, both consisting of $n$ vertices, in his right pocket. Each edge in each tree has its own weight. The $i$-th edge in the first tree has a weight of $a_i$, while the $i$-th edge in the second tree has a pair of weight, denoted by $(b_i, c_i)$.

Let ${}^1\!u$ be the $u$-th vertex in the first tree, and ${}^2\!u$ be the $u$-th vertex in the second tree. Let $\mathbb{E}_1({}^1\!u, {}^1\!v)$ be the set containing the indices of all the edges on the path between the $u$-th and the $v$-th vertex in the first tree. Similarly, let $\mathbb{E}_2({}^2\!u, {}^2\!v)$ be the set containing the indices of all the edges on the path between the $u$-th and the $v$-th vertex in the second tree. Define the following values:

  • $A_{\min}({}^1\!u, {}^1\!v) = \min\{a_k | k \in \mathbb{E}_1({}^1\!u, {}^1\!v)\}$
  • $B_{\max}({}^2\!u, {}^2\!v) = \max\{b_k | k \in \mathbb{E}_2({}^2\!u, {}^2\!v)\}$
  • $C_{\max}({}^2\!u, {}^2\!v) = \max\{c_k | k \in \mathbb{E}_2({}^2\!u, {}^2\!v)\}$

As DreamGrid is bored, he decides to count the number of good indices. DreamGrid considers an index $i$ ($1 \le i \le n$) is good, if for all $1 \le j \le n$ and $j \ne i$, $A_{\min}({}^1\!i, {}^1\!j) \ge \min(B_{\max}({}^2\!i, {}^2\!j), C_{\max}({}^2\!i, {}^2\!j))$. Please help DreamGrid figure out all the valid indices.

Input

There are multiple test cases. The first line contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($2 \le n \le 10^5$), indicating the number of vertices in both trees.

For the following $(n-1)$ lines, the $i$-th line contains three integers ${}^1\!u_i$, ${}^1\!v_i$ and $a_i$ ($1 \le {}^1\!u_i, {}^1\!v_i \le n$, $1 \le a_i \le 10^9$), indicating that there is an edge, whose weight is $a_i$, connecting vertex $u_i$ and $v_i$ in the first tree.

For the following $(n-1)$ lines,the $i$-th line contains four integers ${}^2\!u_i$, ${}^2\!v_i$, $b_i$ and $c_i$ ($1 \le {}^2\!u_i, {}^2\!v_i \le n$, $1 \le b^2_i, c^2_i \le 10^9$), indicating that there is an edge, whose weight is $(b_i, c_i)$, connecting vertex $u_i$ and $v_i$ in the second tree.

It's guaranteed that the sum of $n$ of all test cases does not exceed $1.5 \times 10^5$.

Output

For each test case output $k$ integers ($k$ is the number of valid indices) in one line separated by a space in increasing order, indicating the indices of the valid vertices.

Note that if there is no valid vertex, you should print "-1" instead.

Sample Input

2
2
1 2 1
1 2 2 3
4
1 2 7
1 3 8
1 4 12
1 2 8 8
2 3 9 7
2 4 6 4

Sample Output

-1
3 4

Author: JIANG, Shibiao
Source: The 16th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple
Submit    Status