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!


The first line will contain T ( number of test cases, 1T101 \leq T \leq 10 ).
For each test case there will be n ( number of nodes in the tree, 1n1051 \leq n \leq 10^5 ) and following n-1 lines will contain uivi u_i v_i (1ui,vin1 \leq u_i, v_i \leq n), which means there is an edge between ui u_i and vi 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, 1a,bn1 \leq a, b \leq n for that particular test case.


1 5
1 3
1 2
3 4

4 5



    11% Solution Ratio

    YouKnowWhoEarliest, Aug '20

    shihaBingFastest, 0.0s

    YouKnowWhoLightest, 6.2 MB

    YouKnowWhoShortest, 767B


    Login to submit

    Toph uses cookies. By continuing you agree to our Cookie Policy.