Description

神校 XJ 之学霸兮, Dzy 皇考曰 JC.

摄提贞于孟陬兮, 惟庚寅 Dzy 以降.

纷 Dzy 既有此内美兮, 又重之以修能.

遂降临于 OI 界, 欲以神力而凌♂辱众生.

今 Dzy 有一魞歄图, 其上有 \(n\) 座祭坛, 又有 \(m\) 条膴蠁边.

时而 Dzy 狂 WA 而怒发冲冠, 神力外溢, 遂有 \(k\) 条膴蠁边灰飞烟灭.

而后俟其日 A50 题则又令其复原. (可视为立即复原)

然若有祭坛无法相互到达, Dzy 之神力便会大减, 于是欲知其是否连通.

Input

第一行 \(n, m\)

接下来 \(m\) 行 \(x, y\): 表示 \(m\) 条膴蠁边, 依次编号

接下来一行 \(Q\)

接下来 \(Q\) 行:

每行第一个数 \(k\) 而后 \(k\) 个编号 \(c_1 \sim c_k\): 表示 \(k\) 条边, 编号为 \(c_1 \sim c_k\)

为了体现在线,\(k\) 以及 \(c_1 \sim c_k\) 均需异或之前回答为连通的个数

Output

对于每个询问输出: 连通则为 “Connected”, 不连通则为 “Disconnected” (不加引号).

Sample Input

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
2 7 0 3
6 0 7 4 6
1 2 7
0 5 0 2 13

Sample Output

Connected
Connected
Connected
Connected
Disconnected

Data Range

对于所有数据, 满足:\(n \leq 10^5, m \leq 5 \times 10^5, Q \leq 50000, 1 \leq k \leq 15\), 并且: 数据保证没有重边与自环.

Explanation

此题做法同 bzoj3569, 请出门右转上一题题解.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;
typedef long long lli;
const int maxn = 500100, maxm = 500100;

class IDontKnowWhatThisDoes
{
public:
    struct edge
    {
        int u, v, rnd;
        edge *next;
    };
    int n, root, ecnt;
    edge *edges[maxn], epool[maxm];
    void add_edge(int u, int v)
    {
        edge *p = &epool[++ecnt];
        p->u = u; p->v = v;
        p->next = edges[u]; edges[u] = p;
        return ;
    }
    bool vis[maxn];
    int b[maxn];
    void dfs1(int p)
    {
        vis[p] = true;
        for (edge *ep = edges[p]; ep; ep = ep->next)
            if (!vis[ep->v]) {
                dfs1(ep->v);
            } else {
                ep->rnd = rand();
                b[p] ^= ep->rnd;
                b[ep->v] ^= ep->rnd;
            }
        return ;
    }
    void dfs2(int p)
    {
        vis[p] = true;
        for (edge *ep = edges[p]; ep; ep = ep->next)
            if (!vis[ep->v]) {
                dfs2(ep->v);
                ep->rnd ^= b[ep->v];
                b[p] ^= b[ep->v];
            }
        return ;
    }
    void construct(void)
    {
        root = 1;
        memset(vis, 0, sizeof(vis));
        dfs1(root);
        memset(vis, 0, sizeof(vis));
        dfs2(root);
        return ;
    }
    // Here goes the checking
    int c[64];
    bool judge(int k)
    {
        int now = 0;
        for (int i = 1 << 30; i; i >>= 1) {
            int j = now + 1;
            for (; j <= k; j++)
                if (c[j] & i)
                    break;
            if (j == k + 1)
                continue;
            swap(c[j], c[++now]);
            for (int j = 1; j <= k; j++)
                if (j != now && c[j] & i)
                    c[j] ^= c[now];
        }
        if (c[k])
            return false;
        return true;
    }
} graph;

int n, m, T;

int main(int argc, char** argv)
{
    srand(19990610);
    scanf("%d%d", &n, &m);
    for (int i = 1, a, b; i <= m; i++) {
        scanf("%d%d", &a, &b);
        if (a > b) swap(a, b);
        graph.add_edge(a, b);
    }
    scanf("%d", &T);
    graph.construct();
    int res = 0;
    for (int idx = 1, k; idx <= T; idx++) {
        scanf("%d", &k);
        k ^= res;
        for (int i = 1, x; i <= k; i++) {
            scanf("%d", &x);
            x ^= res;
            graph.c[i] = graph.epool[x].rnd;
        }
        if (graph.judge(k)) {
            printf("Disconnected\n");
        } else {
            res += 1;
            printf("Connected\n");
        }
    }
    return 0;
}