Adelaide University has built a lot of new paths to combine the two old universities during the merger. These paths take quite a scenic route through Adelaide, however, and students have been forming shortcuts that jump directly from an earlier intersection to a later intersection on the same route!

Jack has decided that he wants to find the optimal way to walk between the two universities, including using these shortcuts. He has simplified the route as a series of intersections, numbered from ~0~ to ~N-1~. Jack always starts at intersection ~0~. When an intersection has no further paths, Jack has reached his destination.

At any intersection, there are at most two paths Jack can take. A path either leads to a new intersection further along the route, or encodes a shortcut whose other endpoint is an earlier intersection on Jack's current route. Shortcuts never connect intersections on different branches, and no two shortcuts overlap - that is, no shortcut's target lies within another shortcut's range on any given route.

When Jack takes a shortcut from intersection ~u~ back to intersection ~v~, he skips all intersections strictly between ~v~ and ~u~ on his current route. Jack knows that he will have to walk back to where he came from after his classes are finished, so he needs your help to find a path with the maximum number of intersections he can skip by taking shortcuts.

Input

The first line contains a single integer, ~N~ (~1 \leq N \leq 10^5~), the number of intersections.

Each of the next ~N~ lines contain two integers, ~a~ and ~b~ (~-1 \leq a, b < N~), representing the paths leaving the ~i~-th intersection. If ~a~ or ~b~ is equal to ~-1~, this indicates that there is no path.

Note: If there is a shortcut, it will always be the first path. There will be at most one shortcut per intersection.

Output

Output the maximum number of intersections Jack can skip along any route.

Example

Input 1

7
1 -1
2  3
4 -1
-1 -1
5  6
-1 -1
1 -1

Output 1

2

Intersection ~6~, which is along the path ~0\to 1\to 2\to 4\to 6~, encodes a shortcut whose target is intersection ~1~. This allows the route to be shortened to ~0\to 1\to 6~, skipping ~2~ intersections.

Input 2

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

Output 2

8