Demux Problems Submissions Users Contests Log in Sign up


Zig Zag


Submit solution

Points: 100
Time limit: 2.0s
Memory limit: 128M

Author:
Problem type
Allowed languages
C, C++, Java, Python

You are given a binary trees \(T\) with \(N\) nodes.

A ZigZag path for a binary tree is defined as follow:

  • Choose any node in the \(T\) and a direction (right or left).
  • If the current direction is right, move to the right child of the current node; otherwise, move to the left child.
  • Reverse the direction.
  • Repeat the second and third steps until you can't move in the tree.

length of ZigZag path is defined as the number of edges on that path.

Output the length longest ZigZag path contained in \(T\).

Input

First line contains single integer: \(N\).

Following lines of input describe the \(T\).

First line contains single integer : \(root\)

Next \(N\) lines contains two integers each, index of left child and right child of node with index \(i\). If any of integer is \(-1\) then corresponding child is absent.

Output

Output the length longest ZigZag path contained in \(T\).

Constraints

\(1\) \(\leq\) \(N\) \(\leq\) \(10^5\)

Example

Input

3
1
2 -1
-1 3
-1 -1

Output

2

Note

You can use this template to submit the solution.


Comments

There are no comments at the moment.