题意
给定一张有向图，每次询问给出 \(s,t\)，求从 \(s\to t\) 的路径上（可以有重复点）可能会经过多少个点，每次询问会临时加入 \(k\) 条边。其中，题目给出的图有如下特点：若 \(x\) 能到达 \(z\)，\(y\) 也能到达 \(z\)，那么必然有 \(x\) 能到达 \(y\) 或者 \(y\) 能到达 \(x\)。
Solution
看到有向图上数点什么的，应该一下子就想到缩点。仔细思考题目中给出的特点，发现在缩点之后，它再去掉所有无用的前向边后，就是一棵外向树。我是 shaber 这棵树不能直接 dfs 抠，因为你必须保证删去的是前向边。此时你考虑如何不删去树边，你会发现从根开始每一条前向边会使得提前遍历到某一个点，但是这个点和真正的儿子区别就是入度不为 \(0\) 了，所以直接拓扑然后保留所有把儿子入度变成 \(0\) 的边。
那在没有加边的情况下就变成了啥必题。
现在考虑加一条边。同理如果加前向边，一点用都没有。还是啥必题。如果加返祖边，就判断是否在路径那条链上，然后看起点移到返祖哪里是否更优。如果是树枝边的话，那就看是否在起点子树内并指向当前链。好像看起来也并不麻烦。
但是加两条呢？好像就没那么简单了。
于是考虑进一步转化。我们考虑到每次询问，加入两条边最多会对六个点产生影响，进一步的，可以看作关键点建虚树。这样每次建一棵虚树，然后把两条边加入，然后跑一个朴素的暴力就可以了。
具体就是考虑在重新建出一个大小为 \(6\) 的有向图，然后正图跑一遍起点能到的点集，反图跑一遍终点能到的点集，然后取交就可以了。
Code
// Problem:
// P7737 [NOI2021] 庆典
//
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7737
// Memory Limit: 1 MB
// Time Limit: 2000 ms
#include<bits/stdc++.h>
#define ll long long
#define inf (1<<30)
#define INF (1ll<<60)
#define pb emplace_back
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define siz(a) (int)(a).size()
#define clr(a) memset(a,0,sizeof(a))
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pt(a) cerr<<#a<<'='<<a<<' '
#define pts(a) cerr<<#a<<'='<<a<<'\n'
// #define int long long
using namespace std;
const int MAXN=6e5+10;
int u[MAXN],v[MAXN];
vector<int> g[MAXN];
int tdfn[MAXN],low[MAXN],stk[MAXN],top,tot;
int col[MAXN],scc,cnt[MAXN],in[MAXN];
void Tarjan(int x){
tdfn[x]=low[x]=++tot;stk[++top]=x;in[x]=1;
for(int s:g[x]){
if(!tdfn[s]) Tarjan(s),low[x]=min(low[x],low[s]);
else if(in[s]) low[x]=min(low[x],tdfn[s]);
}if(tdfn[x]==low[x]){
scc++;do{col[stk[top]]=scc;
cnt[scc]++;in[stk[top]]=0;
}while(stk[top--]!=x);
}
}
vector<int> e[MAXN];
int deg[MAXN],rt;
void topo(){
queue<int> q;
rep(i,1,scc) if(!deg[i]) q.push(i),rt=i;
while(!q.empty()){
int x=q.front();q.pop();
for(int s:g[x])
if(--deg[s]==0)
e[x].pb(s),q.push(s);
}
}
int dfn[MAXN],dtot,siz[MAXN],son[MAXN],dep[MAXN],sum[MAXN],fa[MAXN];
void dfs1(int x){
dfn[x]=++dtot;sum[x]+=cnt[x];
siz[x]=1;son[x]=-1;
for(int s:e[x]){
dep[s]=dep[x]+1;sum[s]=sum[x];fa[s]=x;
dfs1(s);siz[x]+=siz[s];
if(son[x]==-1||siz[son[x]]<siz[s])
son[x]=s;
}
}
int Top[MAXN];
void dfs2(int x,int t){
Top[x]=t;if(~son[x]) dfs2(son[x],t);
for(int s:e[x])
if(s!=son[x]) dfs2(s,s);
}
int LCA(int x,int y){
while(Top[x]^Top[y]){
if(dep[Top[x]]<dep[Top[y]]) swap(x,y);
x=fa[Top[x]];
}if(dep[x]<dep[y]) return x;
else return y;
}
struct Edge{int x,y,w;};
vector<Edge> G;
vector<int> se[MAXN],te[MAXN];
int id[MAXN];
void add(int x,int y){
int w=sum[fa[y]]-sum[x];
G.pb(Edge{x,y,w});
se[x].pb(siz(G)-1);
te[y].pb(siz(G)-1);
}
bool cmp(int x,int y){return dfn[x]<dfn[y];}
vector<int> nd;
void build(){
sort(all(nd),cmp);
nd.erase(unique(all(nd)),nd.end());
int tmpsiz=siz(nd);
rep(i,1,tmpsiz-1) nd.pb(LCA(nd[i-1],nd[i]));
sort(all(nd),cmp);
nd.erase(unique(all(nd)),nd.end());
rep(i,0,siz(nd)-1) id[nd[i]]=i;
rep(i,1,siz(nd)-1) add(LCA(nd[i-1],nd[i]),nd[i]);
}
int nw[7];
signed main()
{
freopen("celebration3.in","r",stdin);
freopen("my.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n,m,Q,K;
cin>>n>>m>>Q>>K;
rep(i,1,m){cin>>u[i]>>v[i];g[u[i]].pb(v[i]);}
rep(i,1,n) if(!tdfn[i]) Tarjan(i);
rep(i,1,n) g[i].clear();
rep(i,1,m) if(col[u[i]]!=col[v[i]]){g[col[u[i]]].pb(col[v[i]]);deg[col[v[i]]]++;}
topo();dfs1(rt);dfs2(rt,rt);
while(Q--){
rep(i,0,K*2+1){
cin>>nw[i];
nw[i]=col[nw[i]],nd.pb(nw[i]);
}
build();
for(int i=2;i<=K*2+1;i+=2){
if(nw[i]==nw[i+1]) continue;
G.pb(Edge{nw[i],nw[i+1],0});
se[nw[i]].pb(siz(G)-1);
te[nw[i+1]].pb(siz(G)-1);
}
bitset<20> node[2],edge[2];
queue<int> q;
// for(int V:nd) cerr<<V<<' ';cerr<<'\n';
q.push(nw[0]);node[0][id[nw[0]]]=1;
while(!q.empty()){
int x=q.front();q.pop();
for(int ed:se[x]){
edge[0][ed]=1;
if(!node[0][id[G[ed].y]]){
node[0][id[G[ed].y]]=1;
q.push(G[ed].y);
}
}
}
// cerr<<node[0]<<' '<<edge[0]<<'\n';
q.push(nw[1]);node[1][id[nw[1]]]=1;
while(!q.empty()){
int x=q.front();q.pop();
for(int ed:te[x]){
edge[1][ed]=1;
if(!node[1][id[G[ed].x]]){
node[1][id[G[ed].x]]=1;
q.push(G[ed].x);
}
}
}
// cerr<<node[1]<<' '<<edge[1]<<'\n';
node[0]&=node[1];
edge[0]&=edge[1];
int ans=0;
rep(i,0,siz(nd)-1) if(node[0][i]) ans+=cnt[nd[i]];
rep(i,0,siz(G)-1) if(edge[0][i]) ans+=G[i].w;
cout<<ans<<'\n';
for(int V:nd) se[V].clear(),te[V].clear();
G.clear();nd.clear();
}
return 0;
}