Subway Routes

While taking the subway George, and Peter were determined to find the longest subway route. They found different routes, and declared their route to be the longest route. After arguing and missing their stop, they realized that both of their routes were the longest routes. Looking back at the map, George, and Peter want to find how many subway routes have the longest length. A subway route is considered different from another subway route if at least one of its endpoints is not an endpoint on the other route. It is guaranteed that there is exactly one unique path between any pair of stations. Assume that all tunnels between stations are of the same length.

Input

N ≤ 50000, the number of stations. The next N-1 lines contain two unique integers x, and y, indicating there is a tunnel connecting stations x and y. (1 ≤ x,y ≤ N)

Output

The number of unique subway routes that have the longest length.

Sample Input

10
5 7
7 1
6 1
2 1
2 8
1 9
3 9
10 9
4 9

Sample Output

7

All Submissions
Best Solutions

Point Value: 17 (partial)
Time Limit: 1.00s
Memory Limit: 16M
Added: Aug 10, 2012
Author: Daniel

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

This question is identical to [url]http://wcipeg.com/problem/ccc13s2p3[/url]

Yup... unfortunately, we completely forgot this question existed when designing the Stage 2 problem set.

wtf... Daniel got to solve his own problem?

It looks like case 5 contains at least the following cycle:

259 - 829 - 79 - 24 - 885 - 220 - 753 - 942 - 482 - 952 - 492 - 741 - 259

Other cases may also contain cycles, but I didn't check. Updated data would be nice! :(

Fixed.

To generate a random tree, use a randomly generated [url=http://bit.ly/Nm1JMN]Pruefer sequence[/url].

The limit on the answer is (N-1)*(N-2), which means that it could just barely overflow an int. Looks like this isn't used in the test data, but that would've been mean =P