A genealogist has recorded a family's ancestry as a binary tree rooted at person 1 (each person has at most two recorded children, referred to as their left and right child).

For any level (generation) of the tree, its width is defined as the distance between the leftmost and rightmost recorded person in that generation, counting the gaps where a person's sibling position could have existed but no person was actually recorded there (as if the tree were laid out as a complete binary tree, with every position indexed accordingly, whether or not a person actually occupies it).

Find the maximum width across all generations of the family tree.

The first line contains a single integer KaTeX can only parse string typed expression — the number of people recorded. If KaTeX can only parse string typed expression, the tree is empty.

The second line contains KaTeX can only parse string typed expression integers, the value associated with each person (person KaTeX can only parse string typed expression to person KaTeX can only parse string typed expression).

Each of the next KaTeX can only parse string typed expression lines contains two integers, the left and right child of that person (using KaTeX can only parse string typed expression if a child was not recorded). The tree is rooted at person KaTeX can only parse string typed expression.

Print a single integer — the maximum generation width.