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
karan: 2015-06-25 10:13:11

(BFS&BFS) :D

Last edit: 2015-06-25 10:13:34
Sukeesh: 2015-06-21 20:32:12

BFS + BFS ! .. AC in one go .. :)

Ankush : 2015-06-19 12:36:31

BFS + BFS :D

BALMUKUND SINHA: 2015-06-15 16:21:01

getting tle

Anant Kumar: 2015-06-12 19:43:18

this is a good problem

Mitch Schwartz: 2015-04-08 01:51:00

That's not true either. I think what you mean to say is that it implies that if the test data is not wrong, then it is incomplete. (This is ignoring the possibility of a faulty judge, for simplicity.)

Weak test data is of course a valid quality concern. There are various factors to consider when it comes to that. I don't want to go into details at the moment, but consider some examples of weakness:

1) test data allows a greedy approach to pass, even though that approach will not always produce correct answers.
2) constraints state n <= 10^8, but in the test data we actually have n <= 10^6.
3) test data is missing the case n=0.
4) perfect squares are a tricky case, but they are not included in the test data.
5) test data was generated randomly according to uniform distribution, leading to a situation where 99% of cases can be solved in a trivial way while the other 1% are hard.

I think it's important to consider the nature and severity of the weakness before changing the test data or requesting for it to be changed. Also, consider that many problems were published many years ago, and the problem setter may be inactive. In some cases, it could be a good option to create a new and improved version of the problem instead of trying to modify the old one.

Last edit: 2015-04-08 02:03:28
reggaeguitar: 2015-04-07 22:51:13

Although it doesn't imply that the test data is wrong, it does imply that it is incomplete

Mitch Schwartz: 2014-08-20 08:57:07

@Raj Kamal: Getting AC with wrong code does not imply test data is wrong. (Let W = set of cases for which your code produces wrong answer, and let I = set of cases in the actual input. It could be that the intersection of I and W is empty.)

Getting WA with correct code does imply test data is wrong.

This is not a hard concept.

Raj Kamal: 2014-08-19 22:23:29

The test cases are all wrong. As many have already mentioned, I also got AC for the cases mentioned by Pankaj Saini and others, when my solution was actually clearly wrong,

Just by changing the start node that I was using for my algo, I went from getting a WA to an AC

Last edit: 2014-08-19 22:25:15

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