The little boy is making beads. He has many numbered beads. Each bead has a unique number - an integer in the range from 1 to N. He lays out all the beads on the floor and connects the beads together in an arbitrary way so that no closed loops are formed. Each of the beads in this case is connected to some other bead. It is required to determine what is the maximum number of beads connected in series in the resulting figure.
Input
The first line contains the number N (1 ≤ N ≤ 2500) - the number of beads. In the next N - 1 lines, two integers each - the numbers of the connected beads.
Imprint
Output one number - the desired number of beads.
Examples
| # |
Input |
Output |
| 1 |
2
1 2
| 2 |
| 2 |
5
2 1
23
24
25 |
3 |