Given a tree.
Tree is an undirected connected acyclic graph. Wiki
You should add exactly one edge to the tree so that, total number of articulation points of the resulting graph is minimized. Note that, resulting graph can have self loops or duplicate edges.
Articulation points of a graph are those nodes, if you we delete one of those, the graph will be disconnected means, will have more than one connected component!
The first line will contain T ( number of test cases, $1 \leq T \leq 10$
).
For each test case there will be n ( number of nodes in the tree, $1 \leq n \leq 10^5$
) and following n-1 lines will contain $ u_i v_i $
($1 \leq u_i, v_i \leq n$
), which means there is an edge between $ u_i$
and $ v_i $
on the tree.
It is guaranteed that, the tree is a valid. <br
For each test case you've to print two integers a b if you add an edge between nodes a and b then resulting graph will have minimum articulation points.
There can be multiple possible solutions, you can print any one of them.
Remember, $1 \leq a, b \leq n$
for that particular test case.
Input | Output |
---|---|
1 5 1 5 1 3 1 2 3 4 | 4 5 |