## 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)

ImbaCalvinon May 19, 2013 - 11:35:16 pm UTC hahahaSourSpinachon May 20, 2013 - 2:42:15 pm UTC Re: hahahaAlexon May 20, 2013 - 11:13:31 pm UTC Re: hahahaSourSpinachon Aug 13, 2012 - 4:25:49 am UTC Data Errors259 - 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! :(

Danielon Aug 13, 2012 - 9:31:07 pm UTC Re: Data Errorsbbi5291on Aug 14, 2012 - 1:40:56 am UTC Re: Re: Data ErrorsSourSpinachon Aug 13, 2012 - 3:29:14 am UTC Haha