我们定义满足如下条件的数列是完美的：
- 由 $-1$ 和 $1$ 组成。
- 它的任一前缀和都不小于 $0$ 。
- 数列的各项和为 $0$ 。
下面列出一些完美的数列作为例子：
- $1, 1, 1, -1, -1, -1$
- $1,-1,1,1,-1,-1$
而如下的数列则不完美：
- $-1,1$
- $1,-1,-1,1$
一个完美数列的 NP 值是这个数列的前缀和中最大的那个的值。比如，前文提到的两个完美数列的 NP 值分别为 $3$ 和 $2$ 。
给一棵树，这棵树的每个节点都被赋予了一个权值 $-1$ 或 $1$ ，请找出一条简单路径，使得由这个路径上各点权值组成的数列是完美数列，且这个数列的 NP 值最大。
输入格式
输入包含多个测试数据。
每个测试数据第一行是一个整数 $n$ ，代表这棵树有 $n$ 个节点。
接下来有 $n$ 行，第 $i$ 行有两个用空格分开的数字 $f_i$ 和 $v_i$ ($v_i \in \{-1,1\}$) ，表示第 $i$ 个点的父节点和第 $i$ 个点的权值。节点被编号为 $1$ 到 $n$ ，如果 $f_i=0$ ，那么节点 $i$ 是这棵树的根。
输出格式
对于每个测试数据，输出每棵树的最大 NP 值，如果这样的路径不存在，输出 $0$ 。
样例数据
样例 1 输入
5 0 -1 1 1 1 -1 2 1 2 -1
样例 1 输出
2
子任务
对于 $100\%$ 的数据， $1 \leq n \leq 10^6$ ，且每个测试点所有测试数据的 $n$ 的总和不会超过 $5 \times 10^6$ 。
特别鸣谢楼天城和吉如一提供试题，数据。