You know that:

1. A Trie $T$ is a rooted tree where each edge is labeled with a character. For any vertex $x$ in the Trie, its two children $y$ and $z$ must not have the same character on edges $(x, y)$ and $(x, z)$.
2. Suppose there is a Trie $T$ rooted at $r$. For a node $x$, the string represented by $x$ is the result of concatenating the characters on the edges along the path from the root $r$ to $x$ in order. Specifically, the string represented by the root $r$ is the empty string. It can be proven that strings represented by different vertices are always distinct.
3. A string $S$ exists in the Trie $T$ if and only if there exists a vertex $x$ such that the string represented by $x$ is $S$.
4. The failure tree $F$ is a rooted tree derived from a given Trie $T$, with the same root as $T$, denoted by $r$. Let $S_x$ be the string represented by node $x$. For a non-root node $x$, let $U$ be the longest proper suffix of $S_x$ (a proper suffix is a suffix of $S$ that is not equal to $S$) such that $U$ exists in $T$. Then, $fail_x$ is defined as the vertex in $T$ such that $S_{fail_x} = U$. Note that the empty suffix of $S_x$ always exists in $T$, so $fail_x$ must exist. The edge set of the failure tree $F$ is $\{(x, fail_x) \mid x \in [1, n], x \neq r\}$. It can be proven that these edges form a tree.

You are given a Trie $T$ with $n$ vertices, labeled $1$ to $n$. Its root is unknown. The character set consists of all integers in $[1, n]$.

You have constructed the corresponding failure tree $F$, and then combined the edges of $T$ (directed away from the root) with the edges of $F$ (directed towards the root) to generate a directed graph $G$, containing $n$ nodes and $2n-2$ directed edges. The construction is as follows:

1. For each non-root vertex $u$, $G$ contains an edge $fa_u \to u$, where $fa_u$ is the parent of $u$ in $T$.
2. For each non-root vertex $u$, $G$ contains an edge $u \to fail_u$.

Given the directed graph $G$ with $n$ vertices (edges are given in arbitrary order), you need to:

1. Find the root vertex $r$ of $T$;
2. Determine which edges of $G$ belong to $T$ and which belong to $F$;
3. Find a valid way to label each edge of $T$ with a character (an integer in $[1, n]$) such that $T$ and its corresponding failure tree $F$ are consistent with $G$.

Input

Each test case contains multiple test sets.

The first line of the input contains an integer $T$, representing the number of test cases. For each test case:

The first line contains an integer $n$, the number of nodes in graph $G$.

The next $2n-2$ lines each contain two integers $x, y$, representing a directed edge from $x$ to $y$ in $G$.

Output

For each test case:

• If no valid solution can be found, output No.
• Otherwise, output Yes, followed by $n-1$ lines, each containing three integers $x, y, z\ (1 \le x, y, z \le n)$, representing an edge in $T$ from $x$ to $y$ ($x$ is the parent of $y$), with the edge labeled with character $z$. The output edges must form the tree $T$, and $T$ and its corresponding failure tree must be consistent with $G$.

If there are multiple valid solutions, you may output any one of them.

Constraints

For all data, $1 \le x, y \le n$, $1 \le n \le 10^5$, $\sum n \le 5 \times 10^5$.

Subtasks

1. (8 points) $n \le 50$
2. (10 points) $n \le 300$
3. (9 points) $n \le 2\,000$
4. (26 points) It is guaranteed that for all data, there exists at least one valid solution rooted at node $1$.
5. (47 points) No additional constraints.

Examples

Input 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

Output 1

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