题目描述

JOI 君家附近有一座宽敞的豪宅。豪宅中有 $N$ 个房间，自东向西排成一列。从最东边的房间起，第 $i$ 个房间被称为房间 $i$。对于每个满足 $1 \le i \le N-1$ 的 $i$，房间 $i$ 与房间 $i+1$ 之间由一条走廊相连。走廊可双向通行。从房间进入走廊需要一把钥匙。每把钥匙都有一个称为“类型”的编号，多个钥匙可以具有相同的类型。

从房间 $i$ 或房间 $i+1$ 进入它们之间的走廊，需要一把类型为 $C_i$ 的钥匙。

房间 $i$ 中有 $B_i$ 把钥匙，其类型为 $A_{i,j}$（$1 \le j \le B_i$）。若 JOI 君进入某个房间，他会拾取该房间内的所有钥匙，之后可随时使用这些钥匙进入走廊。

JOI 君可无限次使用钥匙。有时，他会获得多个相同类型的钥匙，但与仅拥有一个该类型钥匙的情况相比，他并无特殊优势。

为应对在豪宅中迷路的情况，JOI 君计划编写一个程序，用于回答以下查询：

• 若 JOI 君在未携带任何钥匙的情况下进入房间 $x$，他能否移动到房间 $y$？

你的任务是编写一个程序，代替 JOI 君回答上述查询。

任务

给定豪宅的信息与查询，编写一个程序，对于每个查询，判断在假设 JOI 君当前未携带任何钥匙的情况下，他是否能从一个房间移动到另一个房间。

输入格式

从标准输入读取以下数据：

• 第一行包含一个整数 $N$，表示豪宅中房间的数量。
• 第二行包含 $N-1$ 个以空格分隔的整数 $C_1, C_2, \ldots, C_{N-1}$。这表示进入连接房间 $i$ 与房间 $i+1$ 的走廊，需要一把类型为 $C_i$ 的钥匙。
• 接下来的 $N$ 行中，第 $i$ 行（$1 \le i \le N$）包含一个正整数 $B_i$，以及 $B_i$ 个以空格分隔的整数 $A_{i,1}, A_{i,2}, \ldots, A_{i,B_i}$。这表示房间 $i$ 中有 $B_i$ 把钥匙，其类型分别为 $A_{i,j}$（$1 \le j \le B_i$）。
• 下一行包含一个整数 $Q$，表示查询的数量。
• 接下来的 $Q$ 行中，第 $k$ 行（$1 \le k \le Q$）包含两个以空格分隔的整数 $X_k, Y_k$。这表示第 $k$ 个查询询问：假设 JOI 君当前未携带任何钥匙，他是否能从房间 $X_k$ 移动到房间 $Y_k$。

输出格式

向标准输出写入 $Q$ 行。第 $k$ 行（$1 \le k \le Q$）若在假设 JOI 君当前未携带任何钥匙的情况下，他能从房间 $X_k$ 移动到房间 $Y_k$，则输出 YES；否则输出 NO。

5
1 2 3 4
2 2 3
1 1
1 1
1 3
1 4
4
2 4
4 2
1 5
5 3

YES
NO
NO
YES

5
2 3 1 3
1 3
1 2
1 1
1 3
1 2
4
1 3
3 1
4 3
2 5

NO
YES
NO
YES

7
6 3 4 1 2 5
1 1
1 5
1 1
1 1
2 2 3
1 4
1 6
3
4 1
5 3
4 7

YES
NO
YES

提示

样例 1 解释

• 在第一个查询中，若 JOI 君按房间 2、1、2、3、4 的顺序访问，他可以到达房间 4。
• 在第二个查询中，他只能访问房间 3 和 4。由于他仅能获得类型为 1 和 3 的钥匙，因此无法到达房间 2。
• 在第三个查询中，他无法从房间 5 获得类型为 4 的钥匙以进入房间 4，因此他无法到达房间 5。
• 在第四个查询中，若他按房间 5、4、3 的顺序访问，他可以到达房间 3。

数据范围

所有输入数据满足以下条件：

• $2 \le N \le 500000$。
• $1 \le Q \le 500000$。
• $1 \le B_1 + B_2 + \cdots + B_N \le 500000$。
• $1 \le B_i \le N$（$1 \le i \le N$）。
• $1 \le C_i \le N$（$1 \le i \le N-1$）。
• $1 \le A_{i,j} \le N$（$1 \le i \le N$，$1 \le j \le B_i$）。
• 对于每个 $i$（$1 \le i \le N$），$B_i$ 个整数 $A_{i,1}, \ldots, A_{i,B_i}$ 互不相同。
• $1 \le X_k \le N$（$1 \le k \le Q$）。
• $1 \le Y_k \le N$（$1 \le k \le Q$）。
• $X_k \ne Y_k$（$1 \le k \le Q$）。

子任务

本题共有 4 个子任务。每个子任务的得分与额外约束如下：

子任务 1 [5 分]

• $N \le 5000$。
• $Q \le 5000$。
• $B_1 + B_2 + \cdots + B_N \le 5000$。

子任务 2 [5 分]

• $N \le 5000$。
• $B_1 + B_2 + \cdots + B_N \le 5000$。

子任务 3 [15 分]

• $N \le 100000$。
• $C_i \le 20$（$1 \le i \le N-1$）。
• $A_{i,j} \le 20$（$1 \le i \le N$，$1 \le j \le B_i$）。

子任务 4 [75 分]

无额外约束。

翻译由 Qwen3-235B 完成