Reduce Articulation Point

ovis96 Intra SUST Programming Co...
Limits 1s, 512 MB · Custom Checker

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!

Input

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

Output

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.

Sample

InputOutput
1
5
1 5
1 3
1 2
3 4


4 5

Submit

Login to submit.

Statistics

14% Solution Ratio
shihaBingEarliest, Aug '20
shihaBingFastest, 0.0s
YouKnowWhoLightest, 6.2 MB
YouKnowWhoShortest, 767B
Toph uses cookies. By continuing you agree to our Cookie Policy.