2-SAT。
建立n个变量，其中第i个变量表示第i个城市是否是首都。
对于边(x,y)，连边x->y'，y->x'。
对于一个有y个城市的国家，新建2y个变量，分别表示前i个城市和后i个城市中是否有首都。
然后求出SCC，判断是否存在合法的方案即可，时间复杂度$O(n+m)$。
#include<cstdio>
const int N=1000010,M=6000010;
int n,m,k,i,x,y,tot,f[N][2],pre[N][2],suf[N][2],q[M],t,from[M];bool v[M];
struct E{int v;E*nxt;}*g[M],*h[M],pool[N*24],*cur=pool,*p;
inline void add(int x,int y){
p=cur++;p->v=y;p->nxt=g[x];g[x]=p;
p=cur++;p->v=x;p->nxt=h[y];h[y]=p;
}
void dfs1(int x){
v[x]=1;
for(E*p=g[x];p;p=p->nxt)if(!v[p->v])dfs1(p->v);
q[++t]=x;
}
void dfs2(int x,int y){
v[x]=0,from[x]=y;
for(E*p=h[x];p;p=p->nxt)if(v[p->v])dfs2(p->v,y);
}
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
int main(){
read(n),read(m),read(k);
for(i=1;i<=n;i++)f[i][0]=++tot,f[i][1]=++tot;
while(m--)read(x),read(y),add(f[x][0],f[y][1]),add(f[y][0],f[x][1]);
while(k--){
read(y);
for(i=1;i<=y;i++){
pre[i][0]=++tot,pre[i][1]=++tot;
suf[i][0]=++tot,suf[i][1]=++tot;
read(x);
add(f[x][1],pre[i][1]);
add(f[x][1],suf[i][1]);
add(pre[i][0],f[x][0]);
add(suf[i][0],f[x][0]);
}
for(i=2;i<=y;i++){
add(pre[i-1][1],pre[i][1]);
add(pre[i-1][1],suf[i][0]);
add(pre[i-1][0],suf[i][1]);
add(suf[i][1],suf[i-1][1]);
add(suf[i][1],pre[i-1][0]);
add(suf[i][0],pre[i-1][1]);
}
}
for(i=1;i<=tot;i++)if(!v[i])dfs1(i);
for(i=tot;i;i--)if(v[q[i]])dfs2(q[i],q[i]);
for(i=1;i<n;i+=2)if(from[i]==from[i+1])return puts("NIE"),0;
return puts("TAK"),0;
}