Graph Problem
给定一张有 n 个顶点、m 条边的有向图,回答 q 组询问。
每组询问给出互不相同的 k1 个顶点 p1,…,pk1 和 k2 对顶点 (si,ti)。暂时删除这些 pj 及其关联边,然后依次判断是否存在从 si 到 ti 的有向路径。
各组删除互相独立。询问端点都不在本组删除集合中。允许 si=ti,此时可以沿长度为0的路径到达自身。
输入格式
第一行两个整数 n,m。
随后 m 行,每行两个整数 u,v,表示有向边 u→v。无自环、无重边。
下一行一个整数 q。
为保证在线作答,后面的顶点编号经过加密。令变量 cnt=0,按下面的顺序处理每一组:
-
第一行先读入 k1,再读入 p1′,…,pk1′,以本组开始时的 cnt 解码:
pj=(pj′+cnt−1)modn+1.
-
第二行先读入 k2,再依次读入 k2 对加密编号 (s′,t′)。每读入一对,立刻用此时的 cnt 解码:
$$s=(s'+cnt-1)\bmod n+1,\qquad t=(t'+cnt-1)\bmod n+1.$$在本组删点后的图中,若 s 能到达 t,该对答案为1,并立刻令 cnt←cnt+1;否则答案为0,cnt 不变。然后才读取、解码下一对。
因此,同一组内后续端点也可能使用已经变化的 cnt;不能等到一组结束后再更新它。已解码的本组删除集合不随之后的 cnt 改变。
保证解码后的 pj 互不相同,所有解码后的 si,ti 都不在本组删除集合中。
输出格式
每组询问输出一行长度为 k2 的二进制字符串,按顺序给出各对的答案。若 k2=0,这一行为空。
数据范围
- 1≤n≤500,0≤m≤n(n−1)。
- 每条边满足 1≤u,v≤n,u=v;无重边。
- 1≤q≤4×105。
- 1≤k1≤min(n−2,6)。
- k2 为非负整数,所有组的 ∑k2≤4×106。
- 所有加密顶点编号 pj′,s′,t′ 均在 [1,n] 内。
保留原题 n 的范围;由于必须存在至少一组合法删除询问,完整合法输入还要同时满足上述 k1 限制。原题没有规定 k2≥1。
样例输入 1
5 4
1 2
2 3
3 4
4 5
2
1 4
2 1 5 1 3
3 5 3 4
1 1 2
样例输出 1
01
1