PT07Z - Longest path in a tree


You are given an unweighted, undirected tree. Write a program to output the length of the longest path (from one node to another) in that tree. The length of a path in this case is number of edges we traverse from source to destination.

Input

The first line of the input file contains one integer N --- number of nodes in the tree (0 < N <= 10000). Next N-1 lines contain N-1 edges of that tree --- Each line contains a pair (u, v) means there is an edge between node u and node v (1 <= u, v <= N).

Output

Print the length of the longest path on one line.

Example

Input:
3
1 2
2 3

Output:
2

hide comments
saurabhshadow: 2020-05-29 20:42:24

If you still stuck at this:
Here is a hint:
- Find the maximum depth node from any node.

nature95: 2020-05-14 13:03:23

Used bfs two times.

offamitkumar: 2020-05-04 19:33:55

AC in single graph traversal . Just keep track of 3 things :
1. Best answer if we don't consider current as root.
2. Best answer if we consider current node as root. i.e. current node connecting two of it's child
3. Best child found till now of current node as this is n-ary tree.

gnuzinhoo: 2020-05-02 16:05:00

I solved it using two bfs

yourmom__: 2020-04-23 08:18:56

Java people, Scanner wont cause TLE in this question. I used scanner and got AC.

zoso_floyd: 2020-04-15 14:42:57

Apply bfs two times. https://www.geeksforgeeks.org/longest-path-undirected-tree/ should help.

aditya_shukla: 2020-03-30 14:26:15

Avoid using Scanner class in Java for taking input.

blackhat_130: 2020-03-26 00:09:01

Beginner level problem for those who want to learn dfs.
Gives me a bit of confidence.

unafraidofdog: 2020-02-10 05:25:13

Last edit: 2020-02-10 07:06:16
bohot_hard_123: 2019-12-23 03:31:46

also many many thanks to @ jame_boy to sharing further in comment box
https://www.youtube.com/watch?v=w9vjFB7m0PM
it took me 1 day to come up with solution a very helpful video

Last edit: 2019-12-23 03:32:10

Added by:Thanh-Vy Hua
Date:2007-03-28
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Co-author Amber