Braised Chicken 热爱 Aho-Corasick 自动机。因此，他提出了以下与 Aho-Corasick 自动机相关的问题。在深入探讨问题之前，他友好地提醒你以下定义：

• Trie $T$ 是一棵有根树，每条边上都写有一个字符。Trie 上的一个顶点 $x$ 不应有两个子节点 $y$ 和 $z$，使得边 $(x, y)$ 和 $(x, z)$ 上写的字符相同。
• 假设给定一棵以 $r$ 为根的 Trie $T$。对于节点 $x$，由 $x$ 表示的字符串是将从 $r$ 到 $x$ 的路径上的边上的字符按其在路径上出现的顺序连接而成的结果字符串。特别地，由 $r$ 表示的字符串是空字符串。可以证明，没有两个不同的顶点表示相同的字符串。
• 当且仅当 Trie $T$ 中存在一个顶点 $x$，使得由 $x$ 表示的字符串为 $S$ 时，我们称字符串 $S$ 存在于 Trie $T$ 中。
• 给定 Trie $T$ 的失配树 $F$ 是一棵以 $T$ 的根 $r$ 为根的树。定义 $S_x$ 为由节点 $x$ 表示的字符串。对于非根节点 $x$，假设 $U$ 是 $S_x$ 的最长真后缀（字符串 $S$ 的真后缀是指不等于 $S$ 本身的 $S$ 的后缀），且 $U$ 存在于 $T$ 中。那么，$fail_x$ 被定义为 $T$ 中的顶点，使得 $S_{fail_x} = U$。注意，$S_x$ 的空后缀总是存在于 $T$ 中，因此 $fail_x$ 总是存在。$F$ 的边集为 $\{(x, fail_x) \mid x \in [1, n], x \neq r\}$。可以证明这些边构成一棵树。

Braised Chicken 有一棵包含 $n$ 个顶点的 Trie $T$，编号为 $1$ 到 $n$。你不知道它的根。字符集是 $[1, n]$ 中的所有整数。然后，他构建了该 Trie 对应的失配树 $F$。之后，他将 $T$ 的边（背离根的方向）和 $F$ 的边（指向根的方向）合并，得到一个包含 $n$ 个节点和 $2n - 2$ 条有向边的无权有向图 $G$。具体来说，$G$ 的构造如下：

• 对于每个非根顶点 $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$ 及其对应的失配树确实符合 $G$。

如果不存在分配根和边信息的有效方法，你也需要报告这一事实。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 5 \times 10^4$)。 接下来是各测试用例的描述。 每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 10^5$)。 随后有 $2n - 2$ 行。每行包含两个整数 $x, y$ ($1 \le x, y \le n$)，表示 $G$ 中从 $x$ 到 $y$ 的一条边。 所有测试用例的 $n$ 之和不超过 $5 \times 10^5$。

输出格式

对于每个测试用例，如果不存在分配根和边信息的有效方法，输出 No。 否则，第一行输出 Yes。然后输出 $n - 1$ 行。每行应包含三个整数 $x, y, z$ ($1 \le x, y, z \le n$)，表示 $T$ 中有一条从 $x$ 到 $y$ 的边（$x$ 应为 $y$ 的父亲），且边上写有字符 $z$。没有任何入边的顶点即为 $T$ 的根。你输出的边必须构成一个与 $G$ 对应的有根 Trie。 你可以按任意顺序打印边。如果存在多种分配 $T$ 的方式，打印任意一种即可。

样例

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

说明

在第一个测试用例中，$T$ 的根是 $4$。可以验证 $fail_1 = 4, fail_2 = 1, fail_3 = 4$。 注意，对于此输入还有其他有效的输出：例如，令 $1$ 为根，$T$ 拥有边 $(1 \to 2, 1), (2 \to 3, 2), (1 \to 4, 2)$（此处 $(x \to y, z)$ 表示 $x$ 是 $y$ 的父亲，且从 $x$ 到 $y$ 的边上写有字符 $z$）也是一个有效的答案。