该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

徐老师已经很好的掌握了单调序列这个概念了！

单调序列分两种：单调递增序列和单调递减序列

而这两种单调序列又分别可以分成两种：严格单调/不严格单调

例如，单调递增序列要求 $a_i >= a_{i-1}$，而严格单调递增序列则要求 $a_i > a_{i-1}$

现在徐老师想到了一个很好的题目：在一棵树上求最长严格单调序列长度

徐老师希望找出一个序列 $a_1 \dots a_k$，其中每个 $a_i$ 均为一个树上结点的编号

这个序列要满足两个条件

1. 这个序列对应的值 $v_{a_i}$ 必须是一个严格单调序列
2. 这个序列中存在一个下标 $x(1 \leq x \leq k)$ 满足在 $2 \leq i \leq x$ 中 $a_{i-1}$ 在以 $a_i$ 为根的子树中，在 $x \leq i \leq k - 1$ 中，$a_{i+1}$ 在以 $a_i$ 为根的子树中

现在徐老师想知道，如果给定一棵树，这个序列长度最长可以是多少？

输入格式

第一行包含两个整数 $n$，表示给定的树有 $n$ 个结点

接下来 $n$ 行，每行包含两个整数 $v_i,father_i$ 表示第 $i$ 个结点的权值和父亲节点编号，其中 $1$ 号点一定是根节点，且 $father_1=0$

输出格式

输出一个整数表示这个序列最长可以是多少

数据范围

对于 $30\%$ 的数据，满足 $father_i=i-1$

对于另外 $30\%$ 的数据，满足 $n \leq 1000$

对于 $100\%$ 的数据，满足 $n \leq 100000，0 \leq v_i \leq 10^9$

样例输入1

4 
10 0
5 1 
5 1
11 3

样例输出1

3

样例输入2

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

样例输出2

10