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.
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≤𝑛≤2⋅1052≤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 2⋅1052⋅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.
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
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 2−32−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.