题目描述

给定一个根为 Vertex $1$ 的有根树，其中顶点编号为 $1, 2, \\dots, N$。

对于顶点 $i \\, (2 \\leq i \\leq N)$，其父节点是 Vertex $P_i$。

给定 $Q$ 个查询。在第 $i$ 个查询 $(1 \\leq i \\leq Q)$ 中，给定整数 $U_i$ 和 $D_i$，找到满足以下条件的顶点 $u$ 的数量：

• 顶点 $U_i$ 在从顶点 $u$ 到根的最短路径上（包括两个端点）。
• 从顶点 $u$ 到根的最短路径上有 恰好 $D_i$ 条边。

约束条件

• $2 \\leq N \\leq 2 \\times 10^5$
• $1 \\leq P_i < i$
• $1 \\leq Q \\leq 2 \\times 10^5$
• $1 \\leq U_i \\leq N$
• $0 \\leq D_i \\leq N - 1$
• 输入中的所有值都是整数。

输入

输入采用以下格式从标准输入给出：

$N$ $P_2$ $P_3$ $\\ldots$ $P_N$ $Q$ $U_1$ $D_1$ $U_2$ $D_2$ $\\vdots$ $U_Q$ $D_Q$

输出

打印 $Q$ 行。第 $i$ 行应包含对第 $i$ 个查询的响应。

示例输入1

7
1 1 2 2 4 2
4
1 2
7 2
4 1
5 5

示例输出1

3
1
0
0

在第 $1$ 个查询中，顶点 $4$、$5$ 和 $7$ 满足条件。在第 $2$ 个查询中，只有顶点 $7$ 满足条件。在第 $3$ 和第 $4$ 个查询中，没有顶点满足条件。