Different Trips

All submissions for this problem are available.
The Chef is enjoying a wonderful vacation in Byteland. What makes the Chef impressed the most is the road system of the country. Byteland has N cities numbered 1 through N. City 1 is the capital of Byteland. The country also has N1 bidirectional roads connecting the cities. The ith road connects two different cities u_{i} and v_{i}. In this road system, people can travel between every pair of different cities by going through exactly one path of roads.
The roads are arranged in such a way that people can distinguish two cities only when both cities have different number of roads connected to it. Such two cities will be considered similar. For example, city A is similar to the capital if the number of roads connected to city A is equal to the number of roads connected to the capital.
On each day during the vacation, the Chef wants to have a trip as follows. He chooses two cities A and B such that the Chef will visit city B if he goes from A to the capital using the shortest path. Then, the Chef will visit the cities on the shortest path from A to B through this path. Please note that A may be equal to B; that means the Chef will enjoy the day in a single city.
The Chef does not want to have similar trips. Two trips are considered similar if and only if
they both have the same number of visited cities and for each i, the ith city visited in one trip is similar to the ith city visited in the other trip.
The Chef wants to have as many different, namely not similar, trips as possible. Help him count the maximum number of possible trips such that no two of them are similar.
Input
The first line of the input contains a single integer N. The ith line of next N1 lines contains two spaceseparated integers u_{i} and v_{i}, denoting the ith road.
Output
Output a single line containing the maximum number of different trips.
Constraints
1 ≤ N ≤ 100000 (10^{5})
u_{i} ≠ v_{i}
Every pair of different cities can be traveled by going through exactly one path of roads.
Sample
Input: 3 2 1 3 1 Output: 3
Explanation
In the sample, the country consists of three cities.
There are two roads. The first road connects city 1 and city 2.
The second road connects city 1 and city 3.
Each day, the Chef can choose the following possible trips:
 A = 1, B = 1
 A = 2, B = 2
 A = 3, B = 3
 A = 2, B = 1
 A = 3, B = 1
However, since the trip (A = 2, B = 2) is similar to the trip (A = 3, B = 3),
and the trip (A = 2, B = 1) is similar to the trip (A = 3, B = 1),
there are only three possible different trips for the Chef.
Author:  tuananh93 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/DIFTRIP 
Tags  dec12, hard, suffixarray, tuananh93 
Date Added:  25092012 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 