Demux Problems Submissions Users Contests Log in Sign up


Min Depth


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.

Output the minimum depth of \(T\).

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf node is a node with no children.

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

Ouput minimum depth of given binary tree.

Constraints

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

Example

Input

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

Output

3

Note

You can use this template to submit the solution.


Comments

There are no comments at the moment.