#include "garden.h"
#include "gardenlib.h"
#pragma GCC optimize("O3")
using namespace std;
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
if(x>y){
x=y;
return true;
}
return false;
}
template<class T, class F>
bool chmax(T &x, F y){
if(x<y){
x=y;
return true;
}
return false;
}
double pass_time=0;
struct namori{
struct uf{
vc<int>par;
uf(int n=0):par(n,-1){}
int root(int x){return (par[x]<0?x:par[x]=root(par[x]));};
int merge(int a,int b){
a=root(a),b=root(b);
if(a==b)return 0;
if(-par[a]<-par[b])swap(a,b);
par[a]+=par[b];
par[b]=a;
return 1;
}
};
int n;
uf u;
vc<int>nxt;
vc<int>group;
vc<int>cyc_len;
vvc<int>orders;
vc<int>TS_order;
vvc<int>inv;
vc<int>belong;
namori(int n):n(n),nxt(n),u(n),group(n),
inv(n),belong(n),TS_order(n){}
void set(int a,int b){
assert(0<=a&&a<n);
assert(0<=b&&b<n);
nxt[a]=b;
}
void build(){
rep(i,n){
inv[nxt[i]].push_back(i);
}
rep(i,n){
u.merge(i,nxt[i]);
}
int g=0;
rep(i,n)if(i==u.root(i))g++;
vc<int>nm(n);
int tmp=0;
rep(i,n){
if(i==u.root(i))nm[i]=tmp++;
}
vvc<int>gs(g);
rep(i,n){
gs[nm[u.root(i)]].push_back(i);
}
cyc_len.resize(g);
orders.resize(g);
vc<int>last_visit(n,-1);
rep(i,g){
vc<int>path;
for(auto&x:gs[i]){
group[x]=i;
}
int T=0;
int now=gs[i][0];
while(1){
if(last_visit[now]!=-1){
REP(j,last_visit[now],T){
orders[i].push_back(path[j]);
TS_order[path[j]]=j-last_visit[now];
belong[path[j]]=1;
}
cyc_len[i]=T-last_visit[now];
break;
}
path.push_back(now);
last_visit[now]=T++;
now=nxt[now];
}
}
}
pair<vc<int>,int> query(int target){
if(!belong[target]){
pair<vc<int>,int>res{};
res.first.resize(n,-1);
res.second=-1;
auto dfs=[&](auto&dfs,int u,int F)->void{
res.first[u]=F;
for(auto&y:inv[u]){
if(belong[y])continue;
dfs(dfs,y,F+1);
}
};
dfs(dfs,target,0);
return res;
}else{
pair<vc<int>,int>res{};
int G=group[target];
res.first.resize(n,-1);
res.second=cyc_len[G];
int a1=TS_order[target];
auto dist=[&](int a,int b,int mod){
if(a<=b)return b-a;
return mod-a+b;
};
for(auto&x:orders[G]){
int a2=TS_order[x];
auto dfs=[&](auto&dfs,int u,int F)->void{
res.first[u]=F;
for(auto&y:inv[u]){
if(belong[y])continue;
dfs(dfs,y,F+1);
}
};
dfs(dfs,x,dist(a2,a1,cyc_len[G]));
}
return res;
}
}
};
vc<int> solve(int n,int m,int p,vc<int>u,vc<int>v,int q,vc<int>k){
/*
いちばん強いところから来た 0~N-1
else : N~2N-1
namoriになるので頑張る
*/
vvc<pair<int,int>>g(n);
rep(i,m){
g[u[i]].push_back({v[i],i});
g[v[i]].push_back({u[i],i});
}
rep(i,n){
sort(all(g[i]),[](auto a,auto b){
return a.second>b.second;
});
}
vc<int>mx(n);
rep(i,n){
mx[i]=g[i].back().second;
}
namori namori(n*2);
//最強から
rep(i,n){
assert(g[i].size());
if(g[i].size()==1){
int number=g[i][0].second;
int go=g[i][0].first;
if(number==mx[go]){
namori.set(i,go);
}else{
namori.set(i,go+n);
}
}else{
int number=g[i][g[i].size()-2].second;
int go=g[i][g[i].size()-2].first;
if(number==mx[go]){
namori.set(i,go);
}else{
namori.set(i,go+n);
}
}
}
//最強から
rep(i,n){
int number=g[i].back().second;
int go=g[i].back().first;
if(number==mx[go]){
namori.set(i+n,go);
}else{
namori.set(i+n,go+n);
}
}
namori.build();
auto R1=namori.query(p);
auto R2=namori.query(p+n);
vc<int>ans(q);
rep(j,q){
rep(i,n){
i+=n;
ans[j]+=
(R1.first[i]==k[j])||
(R2.first[i]==k[j])||
(R1.second!=-1&&R1.first[i]!=-1&&(k[j]>=R1.first[i]&&k[j]%R1.second==R1.first[i]%R1.second))||
(R2.second!=-1&&R2.first[i]!=-1&&(k[j]>=R2.first[i]&&k[j]%R2.second==R2.first[i]%R2.second));
i-=n;
}
}
return ans;
}
/*
vc<int> de(int n,int m,int p,vc<int>u,vc<int>v,int q,vc<int>k){
いちばん強いところから来た 0~N-1
else : N~2N-1
namoriになるので頑張る
vvc<pair<int,int>>g(n);
rep(i,m){
g[u[i]].push_back({v[i],i});
g[v[i]].push_back({u[i],i});
}
rep(i,n){
sort(all(g[i]),[](auto a,auto b){
return a.second>b.second;
});
}
vc<int>mx(n);
rep(i,n){
mx[i]=g[i].back().second;
}
namori namori(n*2);
//最強から
rep(i,n){
assert(g[i].size());
if(g[i].size()==1){
int number=g[i][0].second;
int go=g[i][0].first;
if(number==mx[go]){
namori.set(i,go);
}else{
namori.set(i,go+n);
}
}else{
int number=g[i][g[i].size()-2].second;
int go=g[i][g[i].size()-2].first;
if(number==mx[go]){
namori.set(i,go);
}else{
namori.set(i,go+n);
}
}
}
//最強から
rep(i,n){
int number=g[i].back().second;
int go=g[i].back().first;
if(number==mx[go]){
namori.set(i+n,go);
}else{
namori.set(i+n,go+n);
}
}
namori.build();
auto R1=namori.query(p);
auto R2=namori.query(p+n);
dbg(R1);
dbg(R2);
vc<int>ans(q);
rep(j,q){
rep(i,n){
i+=n;
ans[j]+=
(R1.first[i]==k[j])||
(R2.first[i]==k[j])||
(R1.second!=-1&&R1.first[i]!=-1&&(k[j]>=R1.first[i]&&k[j]%R1.second==R1.first[i]%R1.second))||
(R2.second!=-1&&R2.first[i]!=-1&&(k[j]>=R2.first[i]&&k[j]%R2.second==R2.first[i]%R2.second));
i-=n;
}
}
dbg(ans);
return ans;
}
vvc<int> brute(int n,int m,int p,vc<int>u,vc<int>v,int q,vc<int>k){
vvc<int>ans(q);
vvc<pair<int,int>>g(n);
rep(i,m){
g[u[i]].push_back({v[i],i});
g[v[i]].push_back({u[i],i});
}
rep(j,q){
rep(i,n){
int pre=-1;
int now=i;
rep(t,k[j]){
pair<int,int>nxt{(int)1e9,-1};
for(auto&x:g[now]){
if(x.second!=pre)chmin(nxt,pair<int,int>{x.second,x.first});
}
if(nxt.second!=-1){
now=nxt.second;
pre=nxt.first;
continue;
}
now=g[now][0].first;
}
if(now==p)ans[j].push_back(i);
}
}
return ans;
}
void check(){
while(1){
int ng=0;
int n=10;
int m=20;
vc<int>u(m),v(m);
rep(i,m){
u[i]=rand()%n;
v[i]=rand()%n;
ng|=u[i]==v[i];
}
rep(i,m)REP(j,i+1,m)if(minmax(u[i],v[i])==minmax(u[j],v[j]))ng=1;
vc<int>deg(n);
rep(i,m){
deg[u[i]]++;
deg[v[i]]++;
}
if(*min_element(all(deg))==0)ng=1;
int p=0;
int q=5;
vc<int>k(q);
rep(i,q)k[i]=rand()%7;
if(!ng){
dbg("START");
auto R1=brute(n,m,p,u,v,q,k);
auto R2=solve(n,m,p,u,v,q,k);
int no=0;
rep(i,q){
if(R1[i].size()!=R2[i]){
no=1;
}
}
if(no){
dbg(n,m,p,u,v,q,k);
dbg(R1);
dbg(R2);
de(n,m,p,u,v,q,k);
assert(0);
}
}
}
}*/
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
vc<int>u(M),v(M);
rep(i,M){
u[i]={R[i][0]};
v[i]={R[i][1]};
}
vc<int>p(Q);
rep(i,Q){
p[i]=G[i];
}
for(auto&x:solve(N,M,P,u,v,Q,p))answer(x);
}
/*int main(){
/*int N,M,P;
cin>>N>>M>>P;
int R[M][2];
rep(i,M)rep(j,2)cin>>R[i][j];
int Q;
cin>>Q;
int G[Q];
rep(i,Q){
cin>>G[i];
}
count_routes(N, M, P, R, Q, G);
check();
}
g++ garden/garden.cpp -D t9unkubj
6 6 0
1 2
0 1
0 3
3 4
4 5
1 5
1
6
*/
