CF246E Blood Cousins Return

题目描述

给定一片家族森林，共有 $n$ 个人，编号为 $1$ 到 $n$。每个人至多有一位直接祖先，并且每个人都有一个名字；不同的人可以拥有相同的名字。

若 $a$ 是 $b$ 的直接祖先，则称 $a$ 是 $b$ 的 $1$ 级祖先。对于 $k>1$，如果 $b$ 的直接祖先存在，且 $a$ 是该直接祖先的 $(k-1)$ 级祖先，则称 $a$ 是 $b$ 的 $k$ 级祖先。反过来，如果 $a$ 是 $b$ 的 $k$ 级祖先，则称 $b$ 是 $a$ 的 $k$ 级儿子。

家族关系保证没有环。现在有 $m$ 次询问，每次给出 $v,k$，要求统计编号为 $v$ 的人的所有 $k$ 级儿子中，不同名字的数量。

输入格式

第一行一个整数 $n$，表示人数。

接下来 $n$ 行，第 $i$ 行包含一个字符串 name_i 和一个整数 $r_i$：

• name_i 表示第 $i$ 个人的名字；
• $r_i$ 表示第 $i$ 个人的直接祖先编号；
• 若 $r_i=0$，表示第 $i$ 个人没有直接祖先。

接下来一行一个整数 $m$，表示询问数。

接下来 $m$ 行，每行两个整数 $v,k$，表示一次询问。

输出格式

对每个询问输出一行一个整数，表示不同名字的数量。

样例

样例输入

5
bob 0
alice 1
alice 1
bob 2
carl 2
3
1 1
1 2
2 1

样例输出

1
2
2

数据范围与约定

$1\le n,m\le 10^5$。名字由小写英文字母组成，长度为正。$0\le r_i\le n$，输入关系构成森林。