AT_joisc2017_h.細長い屋敷 (Long Mansion)

#「JOISC 2017 Day 3」幽深府邸

题目译自 JOISC 2017 Day3 T2「細長い屋敷（Long Mansion）」

$N$ 个房间排列在一条直线上，依次编号为 $1, 2, \ldots, N$。只有编号相邻的房间才相连。相连的房间之间有上锁的门。
从房间 $i$ 进入房间 $i+1$，或者从房间 $i+1$ 进入房间 $i$，需要类型为 $C_i$ 的钥匙 $(1\le i\le N-1)$。
进入房间 $i$ 可以捡起房间里的所有钥匙。房间 $i$ 有 $B_i$ 把钥匙，类型分别为 $A[i][1]\dots A[i][B_i]$ 保证对于同一个 $i$，没有两个 $A[i][j]$ 相同。钥匙可以重复使用。你可能会获得相同的钥匙，然并卵。
现在有 $Q$ 组查询，每组查询用两个整数 $x, y$ 来描述 $(x≠y)$，表示：如果有人被丢进房间 $x$，手上没有任何钥匙，此人能否到达房间 $y$（当然，此人可以捡房间 $x$ 里的钥匙）。
对于每组查询，如果此人能到达，输出 $\texttt{YES}$，否则输出 $\texttt{NO}$ 。

第一行有一个整数 $N$。
第二行有 $N-1$ 个整数 $C_1, C_2, \dots, C_{N-1}$，用空格分隔。
在接下来的 $N$ 行中，第 $i$ 行 $(1\le i\le N)$ 的开头有一个整数 $B_i$，后面有 $B_i$ 个整数 $A[i][1]\dots A[i][B_i]$，这 $B_i+1$ 个整数用空格分隔。
第 $N+2$ 行有一个整数 $Q$。
在接下来的 $Q$ 行中，第 $k$ 行 $(1\le k\le Q)$ 有两个整数 $X_k, Y_k$，表示一组查询。

输出共 $Q$ 行，每行一个字符串 $\texttt{YES}$ 或 $\texttt{NO}$ ，表示此人能否到达房间 $y$。

样例

样例输入 1

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

样例输出 1

YES
NO
NO
YES

样例解释 1

查询 1：可行，此人应依次到 $2, 1, 2, 3, 4$ 号房间搜刮钥匙。
查询 2：不可行，此人只能到达 $3,4$ 号房间，只能拿到 $1,3$ 号钥匙。
查询 3：不可行，此人无法拿到 $4$ 号钥匙。
查询 4：可行，此人应依次到 $5, 4, 3$ 号房间搜刮钥匙。

样例输入 2

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

样例输出 2

NO
YES
NO
YES

样例输入 3

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

样例输出 3

YES
NO
YES

对于所有数据，$2\le N\le 5\times 10^5,$ $1\le Q\le 5\times 10^5,$ $1\le \sum B_i \le 5\times 10^5,$ $1\le B_i, C_i, A[i][j], X_k, Y_k\le N,$ $X_k≠Y_k$。

子任务 #	分值	$N$	$Q$	$\sum B_i$	$C_i, A[i][j]$
1	5	$N\le 5000$	$Q\le 5000$	$\sum B_i \le 5000$	.
2	5	$N\le 5000$	.	$\sum B_i \le 5000$	.
3	15	$N\le 10^5$	.	.	$C_i, A[i][j]\le 20$
4	75	.	.	.	.

感谢 Planet6174 提供的翻译