题目描述

我们定义满足如下条件的数列是完美的：

1. 由 $-1$ 和 $1$ 组成。
2. 它的任一前缀和都不小于 $0$。
3. 数列的各项和为 $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$。

样例

输入

5
0 -1
1 1
1 -1
2 1
2 -1

输出

2

数据范围与提示

对于 $100\%$ 的数据，$1 \leq n \leq 10^6$，且每个测试点所有测试数据的 $n$ 的总和不会超过 $5 \times 10^6$。