rt。这份暴力建图加数据点分治过了。建议加一个能爆暴力建图且答案为NIE的数据。

TAK+暴力建图->过了？

虽然这意义不太大，但还是希望加强以下数据。

#include <bits/stdc++.h>
#define MAXN 1000003
using namespace std;
int n,m,k;
vector <int> e[MAXN];
vector <int> part[MAXN];
vector <int> e2[MAXN*2];
int dfn[MAXN*2],low[MAXN*2];
int inx;
int vis[MAXN*2];
int sta[MAXN*2],cnt;
int col[MAXN*2],color;
void tarjan(int u){
    dfn[u]=low[u]=++inx;
    vis[u]=1; sta[++cnt]=u;
    for (int v:e2[u]){
        if (!dfn[v]){
            tarjan(v); low[u]=min(low[u],low[v]); 
        } else if (vis[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if (dfn[u]==low[u]){
        color++; int top;
        do{
            top=sta[cnt]; cnt--;
            vis[top]=0;
            col[top]=color;
        } while (top!=u);
    }
    return;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>k;
    for (int i=1;i<=m;i++){
        int u,v; cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for (int i=1;i<=k;i++){
        int w; cin>>w;
        for (int j=1;j<=w;j++){
            int u; cin>>u;
            part[i].push_back(u);
        }
    }
    int cnt=0;
    for (int i=1;i<=k;i++){
        for (int u:part[i]){
            for (int v:part[i]){
                if (u==v) continue;
                cnt++;
                if (cnt>=10000000){
                    cout<<"TAK\n";
                    return 0;
                }
                e2[u].push_back(v+n);
            }
        }
    }
    for (int i=1;i<=n;i++){
        for (int j:e[i]){
            e2[i+n].push_back(j);
        }
    }
    for (int i=1;i<=n*2;i++){
        if (!dfn[i]){
            tarjan(i);
        }
    }
    int flag=1;
    for (int i=1;i<=n;i++){
        if (col[i]==col[i+n]){
            flag=0;
            break;
        }
    }
    if (flag) cout<<"TAK\n";
    else cout<<"NIE\n";
    return 0;
}