DreamGrid 在他的右口袋里发现了两棵树，每棵树都有 $n$ 个顶点。每棵树中的每条边都有其权重。第一棵树中第 $i$ 条边的权重为 $a_i$，而第二棵树中第 $i$ 条边的权重为一对值，记作 $(b_i, c_i)$。

令 $^1u$ 为第一棵树中的第 $u$ 个顶点，$^2u$ 为第二棵树中的第 $u$ 个顶点。令 $E_1(^1u, ^1v)$ 为第一棵树中连接第 $u$ 个顶点和第 $v$ 个顶点的路径上所有边的索引集合。类似地，令 $E_2(^2u, ^2v)$ 为第二棵树中连接第 $u$ 个顶点和第 $v$ 个顶点的路径上所有边的索引集合。定义以下值：

• $A_{\min}(^1u, ^1v) = \min\{a_k \mid k \in E_1(^1u, ^1v)\}$
• $B_{\max}(^2u, ^2v) = \max\{b_k \mid k \in E_2(^2u, ^2v)\}$
• $C_{\max}(^2u, ^2v) = \max\{c_k \mid k \in E_2(^2u, ^2v)\}$

由于 DreamGrid 很无聊，他决定计算“好”索引的数量。DreamGrid 认为一个索引 $i$ ($1 \le i \le n$) 是好的，如果对于所有 $1 \le j \le n$ 且 $j \neq i$，满足 $A_{\min}(^1i, ^1j) \ge \min(B_{\max}(^2i, ^2j), C_{\max}(^2i, ^2j))$。请帮助 DreamGrid 找出所有有效的索引。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。 对于每组测试数据： 第一行包含一个整数 $n$ ($2 \le n \le 10^5$)，表示两棵树中顶点的数量。 接下来的 $(n - 1)$ 行中，第 $i$ 行包含三个整数 $^1u_i, ^1v_i$ 和 $a_i$ ($1 \le ^1u_i, ^1v_i \le n, 1 \le a_i \le 10^9$)，表示第一棵树中连接顶点 $u_i$ 和 $v_i$ 的边，其权重为 $a_i$。 接下来的 $(n - 1)$ 行中，第 $i$ 行包含四个整数 $^2u_i, ^2v_i, b_i$ 和 $c_i$ ($1 \le ^2u_i, ^2v_i \le n, 1 \le b_i, c_i \le 10^9$)，表示第二棵树中连接顶点 $u_i$ 和 $v_i$ 的边，其权重为 $(b_i, c_i)$。

保证所有测试数据的 $n$ 之和不超过 $1.5 \times 10^5$。

输出格式

对于每组测试数据，在一行中按升序输出 $k$ 个整数（$k$ 为有效索引的数量），表示有效的顶点索引。 注意，如果没有有效的顶点，你应该输出 “-1”。

样例

输入 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