你知道：

1. 所谓一棵 Trie 树 $T$ 是一棵有根树，每条边上写有一个字符。对于 Trie 中的任意顶点 $x$，$x$ 的两个子节点 $y$ 和 $z$ 不应有相同字符写在边 $(x,y)$ 和 $(x,z)$ 上。
2. 假设有一棵以 $r$ 为根的 Trie 树 $T$。对于一个节点 $x$，由 $x$ 表示的字符串是从根 $r$ 到 $x$ 的路径上各边字符按顺序连接起来的结果字符串。特别地，由根 $r$ 表示的字符串是空字符串。可以证明，不同顶点表示的字符串总是不同的。
3. 如果字符串 $S$ 存在于 Trie $T$ 中，当且仅当存在一个顶点 $x$，由 $x$ 表示的字符串是 $S$。
4. 失配树 $F$ 是给定 Trie 树 $T$ 的一棵有根树，根与 $T$ 的根相同，记为 $r$。定义节点 $x$ 表示的字符串为 $S_x$。对于非根节点 $x$，设 $U$ 是 $S_x$ 的最长真后缀（真后缀指 $S$ 的一个后缀，且不等于 $S$），且 $U$ 存在于 $T$ 中。那么，$fail_x$ 定义为满足 $S_{fail_x}=U$ 的 $T$ 中顶点。注意，$S_x$ 的空后缀总存在于 $T$ 中，因此 $fail_x$ 一定存在。失配树 $F$ 的边集为 $\{(x,fail_x) \mid x \in [1,n], x \ne r\}$。可以证明这些边构成一棵树。

现在你有一棵包含 $n$ 个顶点的 Trie 树 $T$，编号为 $1$ 到 $n$。它的根未知。字符集为 $[1,n]$ 中的所有整数。

你构造了对应的失配树 $F$，然后将 $T$ 的边（从根向外的方向）与 $F$ 的边（指向根的方向）组合，生成了一个 有向图 $G$，包含 $n$ 个节点和 $2n-2$ 条有向边。具体构造如下：

1. 对于每个非根顶点 $u$，$G$ 包含一条边 $fa_u \to u$，其中 $fa_u$ 是 $u$ 在 $T$ 中的父节点。
2. 对于每个非根顶点 $u$，$G$ 包含一条边 $u \to fail_u$。

给定包含 $n$ 个顶点的有向图 $G$（边按任意顺序给出），你需要：

1. 找到 $T$ 的根顶点 $r$；
2. 确定 $G$ 的哪些边属于 $T$，哪些边属于 $F$；
3. 找到一种合法的方式为 $T$ 的每条边标注一个字符（字符为 $[1,n]$ 中的整数），使得 $T$ 和对应的失配树 $F$ 符合 $G$。

输入格式：

每个测试点中包含多组测试数据。

输入的第一行包含整数 $T$，表示数据组数。对于每组数据：

输入的第一行包含一个整数 $n$，表示图 $G$ 的节点数。

接下来 $2n-2$ 行，每行包含两个整数 $x,y$ ，表示 $G$ 中从 $x$ 到 $y$ 的一条边。

输出格式：

对于每组测试数据：

• 如果无法找到合法方案，输出一行 No。
• 否则，输出一行 Yes，接着输出 $n-1$ 行，每行包含三个整数 $x,y,z\ (1 \le x,y,z \le n)$，表示 $T$ 中一条从 $x$ 到 $y$ 的边（$x$ 是 $y$ 的父节点），且该边标注的字符为 $z$。输出的边应满足输出的树是 $T$，并且 $T$ 和对应的失配树与 $G$ 相符。

如果有多种合法方案，你可以输出任意一种。

样例输入 1

4
4
1 4
4 1
1 2
2 1
2 3
3 4
2
1 2
1 2
1
3
1 2
2 1
2 3
3 2

样例输出 1

Yes
1 2 1
2 3 2
4 1 1
No
Yes
Yes
1 2 1
2 3 1

子任务

对于所有数据，$1 \le x,y \le n$，$1 \leq n \leq 10^5$，$\sum n \leq 5 \times 10^5$。

子任务一（8 分）

$n \leq 50$

子任务二（10 分）

$n \leq 300$

子任务三（9 分）

$n \leq 2\,000$

子任务四（26 分）

保证对于所有数据，存在至少一组以 $1$ 号点为根的合法的解。

子任务五（47 分）

没有额外的限制。