CF1667D.Edge Elimination

You are given a tree (connected, undirected, acyclic graph) with $n$ vertices. Two edges are adjacent if they share exactly one endpoint. In one move you can remove an arbitrary edge, if that edge is adjacent to an even number of remaining edges.

Remove all of the edges, or determine that it is impossible. If there are multiple solutions, print any.

给你一棵树（连通的、无向的、无环图），该树包含 $n$ 个顶点。若两条边恰好共享一个公共端点，则称这两条边相邻。在一次操作中，你可以移除任意一条边，但前提是该边在当前剩余边集中与偶数条边相邻。

请移除所有边，或判断这是不可能的。若存在多种解法，输出任意一种即可。

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of vertices in the tree.

Then $n-1$ lines follow. The $i$-th of them contains two integers $u_i$, $v_i$ ($1 \le u_i,v_i \le n$) the endpoints of the $i$-th edge. It is guaranteed that the given graph is a tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$），表示树中顶点的数量。

接下来是 $n-1$ 行，其中第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i,v_i \le n$），表示第 $i$ 条边的两个端点。保证所给图是一棵树。

保证所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

For each test case print "NO" if it is impossible to remove all the edges.

Otherwise print "YES", and in the next $n-1$ lines print a possible order of the removed edges. For each edge, print its endpoints in any order.

对于每个测试用例，如果无法移除所有边，则输出 "NO"。

否则输出 "YES"，并在接下来的 $n-1$ 行中输出一种可能的边移除顺序。对于每条边，以任意顺序输出其两个端点。

Test case $1$: it is possible to remove the edge, because it is not adjacent to any other edge.

Test case $2$: both edges are adjacent to exactly one edge, so it is impossible to remove any of them. So the answer is "NO".

Test case $3$: the edge $2-3$ is adjacent to two other edges. So it is possible to remove it. After that removal it is possible to remove the remaining edges too.

测试用例 $1$：可以删除该边，因为它不与任何其他边相邻。

测试用例 $2$：两条边各自恰好与一条边相邻，因此无法删除其中任意一条。答案为“NO”。

测试用例 $3$：边 $2-3$ 与其他两条边相邻，因此可以删除它。删除之后，剩余的边也可被依次删除。