#P18633. Graph Problem

Graph Problem

Graph Problem

给定一张有 nn 个顶点、mm 条边的有向图,回答 qq 组询问。

每组询问给出互不相同的 k1k_1 个顶点 p1,…,pk1p_1,\ldots,p_{k_1} 和 k2k_2 对顶点 (si,ti)(s_i,t_i)。暂时删除这些 pjp_j 及其关联边,然后依次判断是否存在从 sis_i 到 tit_i 的有向路径。

各组删除互相独立。询问端点都不在本组删除集合中。允许 si=tis_i=t_i,此时可以沿长度为0的路径到达自身。

输入格式

第一行两个整数 n,mn,m。

随后 mm 行,每行两个整数 u,vu,v,表示有向边 u→vu\to v。无自环、无重边。

下一行一个整数 qq。

为保证在线作答,后面的顶点编号经过加密。令变量 cnt=0cnt=0,按下面的顺序处理每一组:

  1. 第一行先读入 k1k_1,再读入 p1′,…,pk1′p'_1,\ldots,p'_{k_1},以本组开始时的 cntcnt 解码:

    pj=(pj′+cnt−1) mod n+1.p_j=(p'_j+cnt-1)\bmod n+1.
  2. 第二行先读入 k2k_2,再依次读入 k2k_2 对加密编号 (s′,t′)(s',t')。每读入一对,立刻用此时的 cntcnt 解码:

    $$s=(s'+cnt-1)\bmod n+1,\qquad t=(t'+cnt-1)\bmod n+1.$$

    在本组删点后的图中,若 ss 能到达 tt,该对答案为1,并立刻令 cnt←cnt+1cnt\gets cnt+1;否则答案为0,cntcnt 不变。然后才读取、解码下一对。

因此,同一组内后续端点也可能使用已经变化的 cntcnt;不能等到一组结束后再更新它。已解码的本组删除集合不随之后的 cntcnt 改变。

保证解码后的 pjp_j 互不相同,所有解码后的 si,tis_i,t_i 都不在本组删除集合中。

输出格式

每组询问输出一行长度为 k2k_2 的二进制字符串,按顺序给出各对的答案。若 k2=0k_2=0,这一行为空。

数据范围

  • 1≤n≤5001\le n\le500,0≤m≤n(n−1)0\le m\le n(n-1)。
  • 每条边满足 1≤u,v≤n1\le u,v\le n,u≠vu\ne v;无重边。
  • 1≤q≤4×1051\le q\le4\times10^5。
  • 1≤k1≤min⁡(n−2,6)1\le k_1\le\min(n-2,6)。
  • k2k_2 为非负整数,所有组的 ∑k2≤4×106\sum k_2\le4\times10^6。
  • 所有加密顶点编号 pj′,s′,t′p'_j,s',t' 均在 [1,n][1,n] 内。

保留原题 nn 的范围;由于必须存在至少一组合法删除询问,完整合法输入还要同时满足上述 k1k_1 限制。原题没有规定 k2≥1k_2\ge1。

样例输入 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