Description
给定一张(n)个点(m)条边的无向连通图。共(q)次询问，每次询问给出一个点集(S)，询问有多少个点满足不在(S)中，且删去后使得(S)中的点不全在一个联通分量中。
Solution
把圆方树建出来。那么题目询问的就是(S)中的点形成的极小联通子树中圆点数量减去(|S|)。盲猜是割点数目的意思。
求圆点数量，可以将点权转边权，即 把圆点和其父亲方点之间的边权值设为1。问题转化为求边权和。而求极小联通子树的边权和，就是将(S)中的点按照(dfs)序排列，并首尾相连，计算相邻两点距离的总和，然后除以2。
例如(S)中的点排序后是{(a_1,a_2,a_3,dots,a_k)}，则答案就是(frac{1}{2}*(dis(a_1,a_2)+dis(a_2,a_3)+dots+dis(a_{k-1},a_k)+dis(a_k,a_1)))。
需要注意的是 如果子树中深度最浅点是圆点，那么答案还要+1，因为点权转边权是将父边权设为1，计算时并没有统计到它。
实现的时候建出圆方树以后记得重新遍历一遍，更新新的(dfs)序。
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(){//be careful for long long!
register int x=0,f=1;register char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
while(isdigit(ch)){x=x*10+(ch^'0');ch=getchar();}
return f?x:-x;
}
const int N=1e5+10;
int n,m;
vector<int> r_E[N],E[N<<1];
#define pb(x) push_back(x)
int cnt,dfn[N<<1],low[N],dfc,stk[N],stp;
inline void Tarjan(int nw,int pa=0){
dfn[nw]=low[nw]=++dfc;stk[++stp]=nw;
for(int to:r_E[nw])
if(to^pa){
if(!dfn[to]){
Tarjan(to,nw);
low[nw]=min(low[nw],low[to]);
if(dfn[nw]<=low[to]){
++cnt;
for(int x=0;x^to;--stp){
x=stk[stp];
E[x].pb(cnt),E[cnt].pb(x);
}
E[nw].pb(cnt),E[cnt].pb(nw);
}
}
else low[nw]=min(low[nw],dfn[to]);
}
}
int fa[N<<1],dis[N<<1],dep[N<<1],siz[N<<1],son[N<<1],tp[N<<1],rt,qaq[N];
inline bool cmp(int a,int b){return dfn[a]<dfn[b];}
inline void Dfs_1(int nw){
dfn[nw]=++dfc;
siz[nw]=1;dis[nw]=dis[fa[nw]]+(nw<=n);son[nw]=tp[nw]=0;
for(int to:E[nw])
if(to^fa[nw]){
fa[to]=nw;dep[to]=dep[nw]+1;
Dfs_1(to);siz[nw]+=siz[to];
if(siz[to]>siz[son[nw]])son[nw]=to;
}
}
inline void Dfs_2(int nw){
if(!tp[nw])tp[nw]=nw;
if(son[nw]){tp[son[nw]]=tp[nw];Dfs_2(son[nw]);}
for(int to:E[nw])
if(to^fa[nw]&&to^son[nw])Dfs_2(to);
}
inline int Lca(int x,int y){
while(tp[x]^tp[y]){
if(dep[tp[x]]>=dep[tp[y]])x=fa[tp[x]];
else y=fa[tp[y]];
}
return dep[x]>dep[y]?y:x;
}
inline int Getdis(int x,int y){return dis[x]+dis[y]-2*dis[Lca(x,y)];}
inline void work(){
cnt=n=read(),m=read();
for(int i=1;i<=n;++i)r_E[i].clear();
for(int i=1,tim=n<<1;i<=tim;++i)E[i].clear();
for(int i=1;i<=m;++i){
int u=read(),v=read();
r_E[u].pb(v),r_E[v].pb(u);
}
memset(dfn,0,sizeof(int)*(n+1));
stp=dfc=0,Tarjan(1);
dfc=0;Dfs_1(1),Dfs_2(1);
for(int i=1,Q=read();i<=Q;++i){
int s=read();rt=0;
for(int i=1;i<=s;++i)qaq[i]=read();
sort(qaq+1,qaq+s+1,cmp);
int ans=0;
for(int i=1;i<s;++i)ans+=Getdis(qaq[i],qaq[i+1]);
ans+=Getdis(qaq[s],qaq[1]);
ans=(ans>>1)+(Lca(qaq[1],qaq[s])<=n)-s;
printf("%d
",ans);
}
}
int main(){
// freopen("in.in","r",stdin);freopen("cpp.out","w",stdout);
int T=read();
while(T--)
work();
return 0;
}