Interesting Tour

Wuhan University is one of the most beautiful universities in China, and there are many charming scenic spots in the campus. After observing for several years, iSea find an interesting phenomenon of those spots: many old spots were built organically and not according to some architecture plan, but, strangely, their growth exhibits a similar pattern: the cities started from three points of spots, with each pair being connected by a bidirectional street; then, gradually, new points of spots were added. Any new point of spot was connected by two new bidirectional streets to two different previous points of spots which were already directly connected by a street.

A tourist visiting our university would like to do a tour visiting as many points of spots as possible. The tour can start at any point of spot and must end at the same point of spot. The tour may visit each street at most once and each point of spot at most once except the first point of spot.

Searing in the library, iSea have known how the scenic spots grew. Now he want to find the largest number of different points of spots a single tour can visit.

There are several test cases in the input.

The first line of each case contains three integers N (3 < N <= 1000), indicating the total number of spots.
The next N-3 lines each contain a pair of space-separated integers A, B, indicating that the corresponding point of interest was connected by streets to points A and B. And you can assume both A and B had already connected.

The input terminates by end of file marker.

For each test case, output one integer, indicating the largest number of different points of spots a single tour can visit.

4
1 2
5
1 2
1 2

4
4

iSea@WHU

2010 ACM-ICPC Multi-University Training Contest（12）——Host by WHU