CF1218H.Function Composition

We are definitely not going to bother you with another generic story when Alice finds about an array or when Alice and Bob play some stupid game. This time you'll get a simple, plain text.

First, let us define several things. We define function $F$ on the array $A$ such that $F(i, 1) = A[i]$ and $F(i, m) = A[F(i, m - 1)]$ for $m \gt 1$. In other words, value $F(i, m)$ represents composition $A[...A[i]]$ applied $m$ times.

You are given an array of length $N$ with non-negative integers. You are expected to give an answer on $Q$ queries. Each query consists of two numbers – $m$ and $y$. For each query determine how many $x$ exist such that $F(x,m) = y$.

我们绝不会再次用那种千篇一律的故事来烦扰你了——比如爱丽丝发现了一个数组，或者爱丽丝与鲍勃玩某种愚蠢的游戏。这一次，你将得到一段简单、纯粹的文本。

首先，我们定义若干概念。我们在数组 $A$ 上定义函数 $F$，使得 $F(i, 1) = A[i]$，且当 $m > 1$ 时，$F(i, m) = A[F(i, m - 1)]$。换言之，值 $F(i, m)$ 表示将 $A[\dots A[i]]$ 复合应用 $m$ 次的结果。

你将获得一个长度为 $N$ 的非负整数数组。你需要回答 $Q$ 个查询。每个查询包含两个数：$m$ 和 $y$。对每个查询，请确定满足 $F(x,m) = y$ 的 $x$ 的个数。

The first line contains one integer $N$ $(1 \leq N \leq 2 \cdot 10^5)$ – the size of the array $A$. The next line contains $N$ non-negative integers – the array $A$ itself $(1 \leq A_i \leq N)$. The next line contains one integer $Q$ $(1 \leq Q \leq 10^5)$ – the number of queries. Each of the next $Q$ lines contain two integers $m$ and $y$ $(1 \leq m \leq 10^{18}, 1\leq y \leq N)$.

第一行包含一个整数 $N$ $(1 \leq N \leq 2 \cdot 10^5)$ —— 数组 $A$ 的大小。
第二行包含 $N$ 个非负整数 —— 数组 $A$ 本身 $(1 \leq A_i \leq N)$。
第三行包含一个整数 $Q$ $(1 \leq Q \leq 10^5)$ —— 查询的次数。
接下来的 $Q$ 行中，每行包含两个整数 $m$ 和 $y$ $(1 \leq m \leq 10^{18}, 1\leq y \leq N)$。

Output exactly $Q$ lines with a single integer in each that represent the solution. Output the solutions in the order the queries were asked in.

输出恰好 $Q$ 行，每行一个整数，表示对应查询的解。请按查询提出的顺序输出解。

For the first query we can notice that $F(3, 10) = 1,\ F(9, 10) = 1$ and $F(10, 10) = 1$.

For the second query no $x$ satisfies condition $F(x, 5) = 7$.

For the third query $F(5, 10) = 6$ holds.

For the fourth query $F(3, 1) = 1.$

For the fifth query no $x$ satisfies condition $F(x, 10) = 8$.

对于第一个查询，我们可以注意到 $F(3, 10) = 1,\ F(9, 10) = 1$ 且 $F(10, 10) = 1$。

对于第二个查询，不存在满足条件 $F(x, 5) = 7$ 的 $x$。

对于第三个查询，成立 $F(5, 10) = 6$。

对于第四个查询，成立 $F(3, 1) = 1$。

对于第五个查询，不存在满足条件 $F(x, 10) = 8$ 的 $x$。