There is a rooted tree of n vertices with the root in vertex 1, each vertex has zero or one heavy child linked with a heavy edge, a set of maximal connected heavy edges form a heavy chain. A single vertex can also form a heavy chain, so each vertex belongs to exactly one heavy chain.

Now we want to build a search tree to maintain some information of the original tree. For each heavy chain with k vertices, we construct a segment tree of depth ⌈log22k⌉ to maintain it, with each leaf of the segment tree indicating a vertex on the heavy chain, and the parent of the segment tree's root is the parent of the top vertex of the heavy chian.

Note that in our variant of the segment tree, every leaves have the same depth.

For instance, this is a possible original tree, note that a double slash indicating a heavy edge.

1
// \
2 7
// \\
3 8
// \\
4 9
// \
5 10
/
6

There are 4 heavy chain in this tree. They are:

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

This is the search tree of the previous origin tree, note that the double slash here has no special meaning, just make the search tree looks more beautiful.

o
// \\
o o
// \\ //
o o o
/ \ / \ /
1 2 3 4 5
| | |
o 10 6
/ \
o o
/ \ /
7 8 9

Given such a original tree, your task is to calculate the depth of the search tree. The depth of the root is 1.

Sample Input

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

Sample Output

7

Hint

Note that the input scale is extremely large.

Notes: In this problem, you may need more stack space to pass this problem. We suggest you to add the following code into your main function if you use C++.

int main() {
int size(512<<20); // 512M
__asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size)); // YOUR CODE
...
exit(0);
}

And if you use the code above please DON’T forget to add exit(0); in the end of your main function, otherwise your code may get RE.

Source

Super League of Chinese College Students Algorithm Design 2023, Contest 5