你知道：
- 所谓一棵 Trie 树 $T$ 是一棵有根树，每条边上写有一个字符。对于 Trie 中的任意顶点 $x$，$x$ 的两个子节点 $y$ 和 $z$ 不应有相同字符写在边 $(x,y)$ 和 $(x,z)$ 上。
- 假设有一棵以 $r$ 为根的 Trie 树 $T$。对于一个节点 $x$，由 $x$ 表示的字符串是从根 $r$ 到 $x$ 的路径上各边字符按顺序连接起来的结果字符串。特别地，由根 $r$ 表示的字符串是空字符串。可以证明，不同顶点表示的字符串总是不同的。
- 如果字符串 $S$ 存在于 Trie $T$ 中，当且仅当存在一个顶点 $x$，由 $x$ 表示的字符串是 $S$。
- 失配树 $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$ 条有向边。具体构造如下：
- 对于每个非根顶点 $u$，$G$ 包含一条边 $fa_u \to u$，其中 $fa_u$ 是 $u$ 在 $T$ 中的父节点。
- 对于每个非根顶点 $u$，$G$ 包含一条边 $u \to fail_u$。
给定包含 $n$ 个顶点的有向图 $G$（边按任意顺序给出），你需要：
- 找到 $T$ 的根顶点 $r$；
- 确定 $G$ 的哪些边属于 $T$，哪些边属于 $F$；
- 找到一种合法的方式为 $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 分）
没有额外的限制。