Comet OJ

C1476 [AHOI2013]连通图

内存限制：256 MB 时间限制：1000 ms

题目描述

给定一个连通的无向图和若干个小集合，每个小集合包含一些边。对于每个集合，你需要确定将集合中的边从原来的无向图中删除后该图是否保持连通。

一个图是连通的当且仅当任意两个不同的点之间存在一条路径连接他们。

输入格式

输入的第一行包含两个整数 $n$ 和 $m(l\le n \le 10000, l \le m \le 100000)$，表示无向图的点数和边数，每个点从 $1$ 到 $n$ 标号。

接下来的 $m$ 行表示图的每条边，每行包含两个整数 $a$ 和 $b$——一条边连接的两个端点的标号。保证每对顶点最多被一条边连接。没有一条边连接两个相同的顶点。每条边按照输入的顺序标号为 $1$ 到 $m$。

接下来的一行包含一个整数 $k(1 \le k \le 100000)$，表示需要测试的小集合的个数。接下来的 $k$ 行每行描述一个小集合。每行的第一个数 $c(l \le c \le 4)$ 表示集合中边的个数，接下来有 $c$ 个整数表示集合中边的标号，保证集合中的整数互不相同。

输出

输出 $k$ 行，每行对应一个小集合的测试结果。第 $i$ 行包含“Connected”（没 有引号)，如果给定的图去掉对应的集合中的边仍然连通，否则应该包含一个“Disconnected”。

样例

样例输入 1

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

样例输出 1

Connected
Disconnected
Connected

提示

$N \le 100000$

$M \le 200000$

$K \le 100000$