大致题意： 给你一张\(DAG\)，多组询问，每次问你在起点不为某些点的前提下，到达给定终点的最大距离是多少。
设阈值
由于限制点数总和与\(n\)同阶，因此容易想到去设阈值。
对于限制点数少于\(\sqrt n\)的询问，首先我们可以\(O(n\sqrt n)\)预处理出对于每个点到其距离前\(\sqrt n\)大的点及其距离。
关于这个，可以通过在\(DAG\)上归并转移处理出来。
然后询问时只要\(O(\sqrt n)\)对于给定终点找到第一个非限制点即可。
对于限制点数大于等于\(\sqrt n\)的询问，我们直接\(O(n)\)暴力。
由于这种询问个数不超过\(\sqrt n\)个，因此时间复杂度也是\(O(n\sqrt n)\)的。
代码
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
#define M 200000
#define SN 400
#define Gmax(x,y) (x<(y)&&(x=(y)))
#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)
#define add_(x,y) (e_[++ee_].nxt=lnk_[x],e_[lnk_[x]=ee_].to=y)
using namespace std;
int n,m,sn,fg,ee,ee_,s[N+5],lnk[N+5],lnk_[N+5];struct edge {int to,nxt;}e[M+5],e_[M+5];
class FastIO
{
private:
#define FS 100000
#define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)
#define pc(c) (C==E&&(clear(),0),*C++=c)
#define tn (x<<3)+(x<<1)
#define D isdigit(c=tc())
int T;char c,*A,*B,*C,*E,FI[FS],FO[FS],S[FS];
public:
I FastIO() {A=B=FI,C=FO,E=FO+FS;}
Tp I void read(Ty& x) {x=0;W(!D);W(x=tn+(c&15),D);}
Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
Tp I void write(Ty x) {W(S[++T]=x%10+48,x/=10);W(T) pc(S[T--]);}
Tp I void writeln(Con Ty& x) {write(x),pc('\n');}
I void writeNA() {pc('-'),pc('1'),pc('\n');}
I void clear() {fwrite(FO,1,C-FO,stdout),C=FO;}
#undef D
}F;
class ListDper//预处理
{
private:
int f[N+5][SN+5],g[N+5][SN+5],f_[SN+5],g_[SN+5],used[N+5];
public:
I void Init()//预处理
{
RI i,j,w,k,px,py,pt,ti=0;for(i=1;i<=n;++i) f[i][1]=0,g[i][1]=i;//初始化
for(i=1;i<=n;++i) for(j=lnk[i];j;j=e[j].nxt)//枚举点转移
{
#define Push1 (f_[pt]=f[i][px]+1,used[g_[pt++]=g[i][px++]]=ti)
#define Push2 (f_[pt]=f[k][py],used[g_[pt++]=g[k][py++]]=ti)
++ti,k=e[j].to,px=py=pt=1;W(g[i][px]&&g[k][py]&&pt<=sn)//归并
{
if(used[g[i][px]]==ti) {++px;continue;}//每个点只考虑一次，这里用了时间戳
if(used[g[k][py]]==ti) {++py;continue;}//同上
f[i][px]+1>=f[k][py]?Push1:Push2;//注意转移时距离会加1
}
W(g[i][px]&&pt<=sn) used[g[i][px]]^ti?Push1:++px;//处理剩余点
W(g[k][py]&&pt<=sn) used[g[k][py]]^ti?Push2:++py;//同上
for(w=1;w^pt;++w) f[k][w]=f_[w],g[k][w]=g_[w];//更新数组
}
}
I void Solve(CI x)//求答案
{
RI p=1;W(g[x][p]&&s[g[x][p]]==fg) ++p;//扫一遍求答案
g[x][p]?F.writeln(f[x][p]):F.writeNA();//输出答案
}
}D;
class BruteForceSolver//暴力
{
private:
int dis[N+5];
public:
I void Solve(CI x)
{
RI i,j,ans=-1;for(i=1;i^x;++i) dis[i]=-1e9;dis[x]=0;//初始化赋值
for(i=x;i;--i) for(s[i]^fg&&Gmax(ans,dis[i]),j=lnk_[i];j;j=e_[j].nxt) Gmax(dis[e_[j].to],dis[i]+1);//暴力
~ans?F.writeln(ans):F.writeNA();//输出答案
}
}B;
int main()
{
RI Qtot,i,x,y,z;for(F.read(n,m,Qtot),sn=sqrt(n),i=1;i<=m;++i) F.read(x,y),add(x,y),add_(y,x);//读入+建边
D.Init();W(Qtot--) {for(F.read(x,y),++fg,i=1;i<=y;++i) F.read(z),s[z]=fg;y<sn?D.Solve(x):B.Solve(x);}//处理询问
return F.clear(),0;
}