P14389 [JOISC 2017] 幽深府邸 / Long Mansion

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。

### 样例 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 完成