P10774 BZOJ3563 DZY Loves Chinese

Given an undirected graph $G = (V, E)$, there are $q$ queries. Each query gives an edge set, and you need to determine whether the graph is still 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.

The first line contains two positive integers $n, m$, denoting the number of vertices and edges in the graph. The next $m$ lines each contain two positive integers $u_i, v_i$, denoting the $i$-th edge. Then one line contains $Q$, denoting the number of queries. The next $Q$ lines each start 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 enforce online processing, in each query, $k$ and $c_1, c_2, \dots, c_k$ must all be XORed with the number of previous answers that were connected.

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

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 there are no multiple edges or self-loops in the graph. Translated by ChatGPT 5