代码:
#include <cstdio> #include <cstring> #include <algorithm> #include <cstdlib> #include <vector> using namespace std; #define N 400050 #define M 400050 #define mem(x) memset(x,0,sizeof(x)) int head[N],to[M],nxt[M],n,m,cnt=1; int dfn[N],low[N],vis[M],S[N],tp,bl[N],bcc; int siz[N],fa[N],dep[N],top[N],son[N]; int a[N],la,dis[N],ans; char buf[100000],*p1,*p2; #define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++) int rd() { int x=0; char s=nc(); while(s<'0'||s>'9') s=nc(); while(s>='0'&&s<='9') x=(((x<<2)+x)<<1)+s-'0',s=nc(); return x; } vector<int>V[N]; inline void add(int u,int v) { to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; } void tarjan(int x) { int i; dfn[x]=low[x]=++dfn[0]; for(i=head[x];i;i=nxt[i]) if(!vis[i]) { vis[i]=vis[i^1]=1; S[++tp]=i; if(!dfn[to[i]]) { tarjan(to[i]); low[x]=min(low[x],low[to[i]]); if(low[to[i]]>=dfn[x]) { int t=0,u,v; bcc++; V[bcc].clear(); while(t!=i) { t=S[tp--]; u=to[t],v=to[t^1]; if(bl[u]!=bcc) bl[u]=bcc,V[bcc].push_back(u); if(bl[v]!=bcc) bl[v]=bcc,V[bcc].push_back(v); } } }else low[x]=min(low[x],dfn[to[i]]); } } inline bool cmp(const int &x,const int &y) {return dfn[x]<dfn[y];} void df1(int x,int y) { dfn[x]=++dfn[0]; int i; siz[x]=1; fa[x]=y; dep[x]=dep[y]+1; son[x]=0; dis[x]=dis[y]+(x<=n); for(i=head[x];i;i=nxt[i]) if(to[i]!=y) { df1(to[i],x); siz[x]+=siz[to[i]]; if(siz[to[i]]>siz[son[x]]) son[x]=to[i]; } } void df2(int x,int t) { top[x]=t; if(son[x]) df2(son[x],t); int i; for(i=head[x];i;i=nxt[i]) if(to[i]!=fa[x]&&to[i]!=son[x]) df2(to[i],to[i]); } int lca(int x,int y) { for(;top[x]!=top[y];y=fa[top[y]]) if(dep[top[x]]>dep[top[y]]) swap(x,y); return dep[x]<dep[y]?x:y; } inline void clr() { mem(head); mem(dfn); tp=0; cnt=1; mem(vis); mem(bl); } void df3(int x) { if(x) ans+=(x<=n&&!vis[x]); int i; for(i=head[x];i;i=nxt[i]) { if(x) ans+=dis[fa[to[i]]]-dis[x]; df3(to[i]); } head[x]=0; } void solve() { clr(); n=rd(),m=rd(); int i,x,y; for(i=1;i<=m;i++) x=rd(),y=rd(),add(x,y),add(y,x); bcc=n; for(i=1;i<=n;i++) if(!dfn[i]) tarjan(i); mem(head); cnt=0; for(x=n+1;x<=bcc;x++) { int lim=V[x].size(); for(i=0;i<lim;i++) { add(x,V[x][i]); add(V[x][i],x); } } mem(dfn); mem(vis); df1(1,0); df2(1,1); int q; q=rd(); mem(head); while(q--) { cnt=0; la=rd(); for(i=1;i<=la;i++) a[i]=rd(),vis[a[i]]=1; sort(a+1,a+la+1,cmp); S[tp=1]=0; for(i=1;i<=la;i++) { x=a[i],y=lca(a[i],S[tp]); while(dep[y]<dep[S[tp]]) { if(dep[y]>=dep[S[tp-1]]) { add(y,S[tp]); tp--; if(S[tp]!=y) S[++tp]=y; break; } add(S[tp-1],S[tp]); tp--; } if(S[tp]!=x) S[++tp]=x; } while(tp>1) add(S[tp-1],S[tp]),tp--; ans=0; df3(0); printf("%d\n",ans); for(i=1;i<=la;i++) vis[a[i]]=0; } } int main() { int T; T=rd(); while(T--) solve(); }