← 返回题目列表

Codeforces · 1200/F

F. 图旅行者

中文机器翻译题面 查看原题

Gildong 正在试验一个有趣的机器 Graph Traveler。在 Graph Traveler 中,有一个由 $$$n$$$ 顶点组成的有向图,编号从 $$$1$$$ 到 $$$n$$$。第 $$$i$$$ 个顶点具有 $$$m_i$$$ 出边,标记为 $$$e_i[0]$$$、$$$e_i[1]$$$、$$$\ldots$$$、$$$e_i[m_i-1]$$$,每个表示边的目标顶点。该图可以有多个边和自环。第 $$$i$$$ 个顶点本身也写有一个整数 $$$k_i$$$。

该图上的行程工作原理如下。

1. Gildong 选择一个起始点和一个整数。将变量 $$$c$$$ 设置为该整数。
2. 到达顶点$$$i$$$后,或者当Gildong在某个顶点$$$i$$$开始旅行时,将$$$k_i$$$添加到$$$c$$$。
3. 下一个顶点是 $$$e_i[x]$$$,其中 $$$x$$$ 是整数 $$$0 \le x \le m_i-1$$$ 满足 $$$x \equiv c \pmod {m_i}$$$。转到下一个顶点并返回步骤 2。

显然,旅行永远不会结束,因为第二步和第三步将无休止地重复。

例如,假设 Gildong 从顶点 $$$1$$$ 开始,其中 $$$c = 5$$$,$$$m_1 = 2$$$、$$$e_1[0] = 1$$$、$$$e_1[1] = 2$$$、$$$k_1 = -3$$$。在他从顶点 $$$1$$$ 开始之后,$$$c$$$ 就变成了 $$$2$$$。由于唯一的整数 $$$x$$$ ($$$0 \le x \le 1$$$) 其中 $$$x \equiv c \pmod {m_i}$$$ 是 $$$0$$$,Gildong 转到顶点 $$$e_1[0] = 1$$$。再次到达顶点$$$1$$$后,$$$c$$$变为$$$-1$$$。唯一满足条件的整数$$$x$$$是$$$1$$$,所以他去顶点$$$e_1[1] = 2$$$,依此类推。

由于 Gildong 非常好奇,他会问你 $$$q$$$ 问题。他想知道如果他从具有特定值 $$$c$$$ 的某个顶点开始旅行,有多少个不同的顶点将被无限次访问。请注意,您不应计算仅被访问有限次的顶点。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 1000$$$),即图中的顶点数。

第二行包含 $$$n$$$ 整数。第 $$$i$$$ 个整数是 $$$k_i$$$ ($$$-10^9 \le k_i \le 10^9$$$),即写在第 $$$i$$$ 个顶点上的整数。

接下来 $$$2 \cdot n$$$ 行描述每个顶点的边。 $$$(2 \cdot i + 1)$$$-st 行包含一个整数 $$$m_i$$$ ($$$1 \le m_i \le 10$$$),即第 $$$i$$$ 个顶点的出边数。 $$$(2 \cdot i + 2)$$$-nd 行包含 $$$m_i$$$ 整数 $$$e_i[0]$$$、$$$e_i[1]$$$、$$$\ldots$$$、$$$e_i[m_i-1]$$$,每个整数值在 $$$1$$$ 和 $$$n$$$ 之间(含)。

下一行包含一个整数 $$$q$$$ ($$$1 \le q \le 10^5$$$),即 Gildong 想要询问的查询数量。

接下来的 $$$q$$$ 行包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$1 \le x \le n$$$, $$$-10^9 \le y \le 10^9$$$),这意味着起始顶点是 $$$x$$$,$$$c$$$ 的起始值为 $$$y$$$。

输出

对于每个查询,如果 Gildong 从顶点 $$$x$$$ 开始,起始整数 $$$y$$$,则打印将被无限多次访问的不同顶点的数量。

示例

输入 #1

4
0 0 0 0
2
2 3
1
2
3
2 4 1
4
3 1 2 1
6
1 0
2 0
3 -1
4 -2
1 1
1 5

输出 #1

1
1
2
1
3
2

输入 #2

4
4 -5 -3 -1
2
2 3
1
2
3
2 4 1
4
3 1 2 1
6
1 0
2 0
3 -1
4 -2
1 1
1 5

输出 #2

1
1
1
3
1
1

注意

第一个示例如下图所示:

在第 $$$i$$$ 个顶点上标记了三个整数:分别为 $$$i$$$、$$$k_i$$$ 和 $$$m_i$$$。出边用一个整数标记,表示第 $$$i$$$ 个顶点的边编号。

每个查询的行程工作如下。它被描述为一系列短语,每个短语的格式为“顶点(添加 $$$k_i$$$ 之后的 $$$c$$$)”。

- $$$1(0) \到 2(0) \到 2(0) \到 \ldots$$$
- $$$2(0) \到 2(0) \到 \ldots$$$
- $$$3(-1) \到 1(-1) \到 3(-1) \到 \ldots$$$
- $$$4(-2) \to 2(-2) \to 2(-2) \to \ldots$$$
- $$$1(1) \到 3(1) \到 4(1) \到 1(1) \到 \ldots$$$
- $$$1(5) \到 3(5) \到 1(5) \到 \ldots$$$

第二个示例与第一个示例相同,只是顶点具有非零值。因此,查询的答案也与第一个示例不同。

第二个示例的查询工作方式如下:

- $$$1(4) \到 2(-1) \到 2(-6) \到 \ldots$$$
- $$$2(-5) \到 2(-10) \到 \ldots$$$
- $$$3(-4) \到 1(0) \到 2(-5) \到 2(-10) \到 \ldots$$$
- $$$4(-3) \到 1(1) \到 3(-2) \到 4(-3) \到 \ldots$$$
- $$$1(5) \到 3(2) \到 1(6) \到 2(1) \到 2(-4) \到 \ldots$$$
- $$$1(9) \到 3(6) \到 2(1) \到 2(-4) \到 \ldots$$$