该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

在图论中，仙人掌图是指：对于图中的每条边，其最多处于一个简单环内的图。如下图所示。注意：树也是仙人掌图；两个点之间恰好有两条边也构成一个简单环。

你现在画出了一棵十分美丽的仙人掌，但是你的好朋友把其中某些边给擦掉了，只给你剩下了一棵树！现在，你只记得剩下的这棵树上的每条边当初所在的简单环的边数 $c_i$。你想要根据这些 $c_i$ 来还原出任意一棵符合要求的仙人掌图，即通过给树上的两个点之间添加边来进行还原。

Input

第一行输入一个正整数 $T$（$1 \le T \le 10^4$），表示数据组数。

对于每一组数据，第一行输入一个正整数 $n$（$2 \le n \le 2 \times 10^5$），表示点数。

接下来 $n-1$ 行，每行输入三个正整数 $u, v, c$（$1 \le u, v, c \le n$, $u \ne v$），表示树上的一条连接点 $u, v$ 的边，这条边之前所在的简单环的边数为 $c_i$。如果 $c_i = 1$，说明这条边之前不属于任意一个简单环。保证输入是一棵树。

数据保证单个测试点 $\sum n \le 2 \times 10^5$。

Output

对于每一组数据，如果不存在一棵符合要求的仙人掌图，说明你的记忆出现了问题，输出一行一个数 -1。

否则，第一行输出添加的边数 $m$，然后接下来 $m$ 行，每行输出两个正整数 $x_i, y_i$，表示你在点 $x_i$ 和 $y_i$ 之间添加了一条新边。如果有多解，输出任意一种解即可。

Samples

2
7
1 2 3
1 6 3
2 3 4
2 5 4
3 4 4
5 7 1
4
1 4 4
1 2 4
2 3 3

2
2 6
5 4
-1