Demux Problems Submissions Users Contests Log in Sign up


Max 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 maximum depth of \(T\).

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

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 YES if trees are similar, otherwise print NO.

Constraints

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

Example

Input

3
2
2 3 1
-1 -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.