#P3569. DZY Loves Chinese II

    ID: 2767 传统题 1000ms 64MiB 尝试: 2198 已通过: 549 难度: 9 上传者: 标签>难度分类提高+/省选-随机化与近似随机赋权检测线性代数与代数线性基树算法树上差分异或消元CF2600

DZY Loves Chinese II

DZY Loves Chinese II

题目描述

给定一张有 nn 个顶点、mm 条边的连通无向图。图中没有重边或自环。

每组询问指定若干条边,判断从原图中删去这些边后,图是否仍然连通。每次询问相互独立;回答后恢复被删去的边。

输入格式

第一行两个整数 n,mn,m。接下来 mm 行每行两个整数 u,vu,v,表示一条无向边。边按输入顺序从 11 到 mm 编号。

接下来一行一个整数 qq,表示询问数。此后 qq 行,每行先给出边数 kk,再给出 kk 个经过编码的边编号。设此前有 ss 次询问回答为 Connected,则把当前行的每个编码编号分别与 ss 按位异或,即得到对应的实际边编号。首问的 s=0s=0。行首的 kk 直接读取。

输出格式

对每组询问输出一行。图仍连通时输出 Connected;否则输出 Disconnected。

样例

5 10
2 1
3 2
4 2
5 1
5 3
4 1
4 3
5 2
3 1
5 4
5
1 1
3 7 0 3
4 0 7 4 6
2 2 7
4 5 0 2 13
Connected
Connected
Connected
Connected
Disconnected

数据范围

1≤n≤1051\le n\le10^5,1≤m≤5×1051\le m\le5\times10^5,1≤q≤5×1041\le q\le5\times10^4,1≤k≤151\le k\le15。

题源署名:dzydaxueba。