Largest cycle in a tree
Tag(s):

Binary/ N-ary Trees, Data Structures, Diameter, Easy, Tree

Problem
Editorial
Analytics

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$

SAMPLE INPUT
7
1 2
1 3
2 4
2 5
3 6
3 7
SAMPLE OUTPUT
4 6
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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...

Contributor

Challenge Name

Cars24 Java Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Dynamic Programming
• Math > Basic Math