题目描述

JSOI 集训队的小 L，小 H，小 X 在紧张的训练之余，总是喜欢玩一个称之为“取数”的游戏来调节自己：

这是一个人玩的游戏，仅仅需要一张白纸和一支笔。玩家在纸上随机写下一行共 $n$ 个整数，形成一个数列，就可以开始游戏了。

每次玩家从原数列最左端或最右端选择一个数，将它从原数列中划去，并写在下一行。当原数列的数全部被划去后，在第二行就出现了一个新的长度为 $n$ 的数列，记为 $S$。将按照如下方式计算数列 $S$ 的分数 $P$：

$$P=S_1\times 5^0+S_2\times 5^1+\cdots+S_n\times 5^{n-1} $$

算出分数 $P$ 后，将其转为二进制表示，如果末三位数字是 $011$ 的话，玩家就取得了游戏的胜利，否则就失败了。

在玩了很多次这个游戏后，小 L，小 H，小 X 发现一个重要的事实：对于某些随机写下的数列，是无论如何也无法取得游戏胜利的，这样的数列被称为“刁列”，其它的数列则被 称为“良列”。

这个游戏虽然趣味性极强，但有一个弊端：每次游戏前需要花很多时间来写出这个随机数列，这一点一直深深困扰着小 L，小 H 和小 X。

直到在今年省选前的那天晚上，小 L 想出了一个惊为天人的创意，一举攻克了这个难题：他们先在纸上画出一颗庞大的无根树（共 $m$ 个结点），每个结点上写下一个整数。当想要玩游戏时，玩家只需随便选择两个结点，通过找出连接这两个结点的那条唯一的路径，将路径上所有结点（包括两个端点）上标注的整数按路径的顺序列出来，就得到了一个数列，然后就可以在这个数列上玩游戏了。如果选择的两个端点分别是树上结点 $v_i$ 和结点 $v_j$，得到的数列就简记为 $i\sim j$。当然，如前所述，$i\sim j$ 这个数列也有“良列”和“刁列”两种可能。

他们发现这样改进以后真的方便了很多！不仅如此，还给游戏带来了一些新的趣味。比如小 X 就声称他发现了一个重要的规律：数列的属性是具有传递性的，即：对于任意互不相同的 $i,j,k$ 有：

• 如果 $i\sim j$ 是良列，$j\sim k$ 是良列，则 $i\sim k$ 是良列。

• 如果 $i\sim j$ 是刁列或 $j\sim k$ 是刁列，则 $i\sim k$ 是刁列。

这个结论出奇地优美，但很快就被小 H 找到了反例，这让小 X 心情沮丧。小 L 为了安慰小 X，说：不如我们来看看你这个结论在多少情况下是成立的吧。

小 X 振作了起来，大家一起投入了繁重的工作中。他们要找出存在多少个三元组 $(i,j,k)$，其中 $i<j<k$，使得 $i,j,k$ 满足小 X 发现的传递性结论。

输入格式

第一行一个整数 $m$，代表无根树的节点个数。

接下来 $m$ 行，每行两个整数 $f_i,x_i$，其中 $f_i<i$。$f_i$ 表示节点 $v_i$ 的父节点编号，如果 $f_i=0$ 则该节点为根，$x_i$ 表示节点 $v_i$ 上写的数。

输出格式

一行一个整数，表示答案。

3
0 3
1 5
1 7

0

5
0 8626
1 29255
2 21486
2 26193
1 22439

7

提示

数据范围

对于 $10\%$ 的数据，$1\leq m\leq 5$。

对于 $30\%$ 的数据，$1\leq m\leq 100$。

对于 $50\%$ 的数据，$1\leq m\leq 10^3$。

对于 $100\%$ 的数据，$1\leq m\leq 10^5$。