当前没有测试数据。

题目描述

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 aia_iai​, 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:

$Amin​({}^1\!u, {}^1\!v)=min{\{ak​∣k∈E1​({}^1\!u, {}^1\!v)}\}$

$Bmin​({}^2\!u, {}^2\!v)=min{\{bk​∣k∈E2​({}^2\!u, {}^2\!v)}\}$

$Cmin​({}^2\!u, {}^2\!v)=min{\{ck​∣k∈E2​({}^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.

You may have seen this problem before, but this time we need you to have an $O(N \log N)$ solution, or it may not pass.

输入格式

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 ai($a_i (1 \le {}^1\!u_i, {}^1\!v_i \le nai​($, $)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 $2 \times 10^5$.

输出格式

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

样例

样例输入 1

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

样例输出 1

-1
3 4