2-SAT。

建立n个变量，其中第i个变量表示第i个城市是否是首都。

对于边(x,y)，连边x->y'，y->x'。

对于一个有y个城市的国家，新建2y个变量，分别表示前i个城市和后i个城市中是否有首都。

然后求出SCC，判断是否存在合法的方案即可，时间复杂度$O(n+m)$。

 

#include
     
      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