Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Reduce Articulation Point

By ovis96 · 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.

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

    Discussion

    Statistics


    11% Solution Ratio

    YouKnowWhoEarliest, 1M ago

    shihaBingFastest, 0.0s

    YouKnowWhoLightest, 6.2 MB

    YouKnowWhoShortest, 767B

    Submit

    Login to submit