TRIBE2 - Tribe Council

The Kazooba tribe contains N men, who want to gather for a tribe council. The men are all descendants of a single one, who is the chief of the tribe. Since the people of this tribe are quite long lived, every person's ancestors, including the chief, are alive and will be attending the council.

The men arrive at the council in some particular order and they are seated as they arrive. The men sit in a row of parallel tables. The first table is at the base of the Holy Mountain and the row extends indefinitely to the West (away from the Mountain). Unfortunately, each man doesn't get along with his father and his sons, so he doesn't want to sit at the same table with any of them. On the other hand, each man wants to be as close to divinity as possible, so, when he arrives at the council, he goes to the table closest to the Holy Mountain, where none of his children or father is already seated.

As usual, the Gods of the tribe have a certain inclination for grandeur. Therefore, they would like to command the men to arrive in such an order, as to maximize the number of tables that are occupied. Unfortunately, they do not have any inclination for programming, so they have ordered you to write a program for that.

Write a program that determines the maximum number of tables that can end up being occupied.

Input

The first line of the input file contains an integer N, representing the number of men in the tribe. All men are numbered from 1 to N; the chief is number 1. Each of the following lines describe a father–son relation and contains two integers A B separated by a blank, meaning that person number A is the father of the person number B. The relations described in the file are correct (for instance, there are no "cycles" and each person is a descendent of the chief).

Output

The output file should contain a single line with the maximum number of tables that can be occupied.

Example

Input:
5
1 4
3 2
1 3
3 5

Output:
3

Explanation

If men arrive in the order 2 4 1 5 3, the following happens:

  • 2 goes to the first table.
  • 4 goes to the first table.
  • 1 has a son (4) at the first table, so he goes to the second table.
  • 5 goes to the first table.
  • 3 has two sons at the first table (2 and 5) and his father (1) is at the second table, so he goes to the third table.

Constraints

  • 1 < N <= 100 000
  • Any table has unlimited capacity.

Note: The problem statement and test data was updated on 22-11-2008. I'm sorry for the inconvenience.


Added by:Ajay Somani
Date:2008-11-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:BOI 2003

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.