[Solution] Edge Elimination solution codeforces

Edge Elimination solution codeforces – 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.

[Solution] Edge Elimination solution codeforces

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

Input

The input consists of multiple test cases. The first line contains a single integer 𝑡t (1𝑡1051≤t≤105) — 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𝑛21052≤n≤2⋅105) — the number of vertices in the tree.

Then 𝑛1n−1 lines follow. The 𝑖i-th of them contains two integers 𝑢𝑖ui𝑣𝑖vi (1𝑢𝑖,𝑣𝑖𝑛1≤ui,vi≤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 21052⋅105.

[Solution] Edge Elimination solution codeforces

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

Otherwise print “YES”, and in the next 𝑛1n−1 lines print a possible order of the removed edges. For each edge, print its endpoints in any order.

Example
input

Copy
5
2
1 2
3
1 2
2 3
4
1 2
2 3
3 4
5
1 2
2 3
3 4
3 5
7
1 2
1 3
2 4
2 5
3 6
3 7

[Solution] Edge Elimination solution codeforces

output

Copy
YES
2 1
NO
YES
2 3
3 4
2 1
YES
3 5
2 3
2 1
4 3
NO

Edge Elimination solution codeforces

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

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

Test case 33: the edge 232−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.

For Solution

Click here

Leave a Comment