SOLVE

LATER

Largest cycle in a tree

/

You are given a tree of $$N$$ nodes and $$N - 1$$ edges. Now you need to select two nodes $$a$$ and $$b$$ in the tree such that the cycle that will be formed after adding an edge between the two nodes $$a$$ and $$b$$, its length should be maximum. If there are more than one possible answers, you can output any of them.

**Input**

The first line contains an integer $$N$$ as input. Next $$N-1$$ lines contain a pair of integers $$(a , b)$$ that denote there is an edge between the two nodes $$a$$ and $$b$$ in the tree.

**Output**

In the output, you need to print two integers separated by space which denote the nodes between which you can add the edge so as to maximize the length of the cycle in the tree.

**Constraints**

**\(1 \le N \le 10^5\)**

Explanation

If you add an edge between the nodes 4 and 6 then you see that it forms the largest cycle in the tree. Some other possible outputs are - 5 6 or 5 7.

Time Limit:
2.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...