Problem Description

Given an undirected graph $G = (V, E)$, there are $q$ queries. Each query gives an edge set. Determine whether the graph is connected after deleting this edge set. It is guaranteed that the size of the edge set does not exceed $15$. The queries are forced online.

Input Format

The first line contains two positive integers $n, m$, representing the number of vertices and edges of the graph.

The next $m$ lines each contain two positive integers $u_i, v_i$, representing the $i$-th edge.

Then a line contains $Q$, the number of queries.

The next $Q$ lines: each line starts with an integer $k$, followed by $k$ positive integers $c_1, c_2, \dots, c_k$, representing an edge set of size $k$, where $c_i$ is the index of an edge.

To force online processing, each $c_1, c_2, \dots, c_k$ must be XORed with the number of previous answers that were connected.

Output Format

For each query output: Connected if the graph is connected, otherwise output Disconnected (without quotes).

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

Hint

Constraints: $1\leq n\leq 10^5$, $1\leq m\leq 5\times 10^5$, $1\leq Q\leq 5\times 10^4$, $1\leq k\leq 15$. It is guaranteed that the graph has no multiple edges or self-loops.

Translated by ChatGPT 5