#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 4e6+10;
int n, mark[maxn], p[maxn], ordc[maxn], nx[maxn], disp[maxn], szc[maxn];
vector<pair<int,int>> g[maxn];
void dfsc(int v, int ini) {
p[v] = v;
disp[v] = 0;
if(nx[v] == ini) {
szc[mark[v]] = ordc[v]+1;
return;
}
ordc[nx[v]] = ordc[v]+1;
dfsc(nx[v],ini);
}
void dfs(int v, int cur) {
mark[v] = cur;
if(mark[nx[v]] == cur) {
//temos um ciclo
ordc[nx[v]] = 0;
dfsc(nx[v],nx[v]);
return;
}
else if(mark[nx[v]] == -1){
dfs(nx[v],cur);
}
if(p[v] == -1) {
disp[v] = disp[nx[v]]+1;
p[v] = p[nx[v]];
}
}
void count_routes(int32_t N, int32_t M, int32_t P, int32_t R[][2], int32_t Q, int32_t G[]) {
n = N;
for(int i = 0; i < M; i++) {
g[R[i][0]].pb(mp(i,R[i][1]));
g[R[i][1]].pb(mp(i,R[i][0]));
}
for(int i = 0; i < n; i++)
sort(all(g[i]));
for(int i = 0; i < n; i++) {
nx[i] = g[i][0].sc;
if(g[nx[i]][0].sc == i)
nx[i]+= n;
if(g[i].size() == 1)
nx[i+n] = g[i][0].sc;
else
nx[i+n] = g[i][1].sc;
if(g[nx[i+n]][0].sc == i)
nx[i+n]+= n;
// cout << i << " " << nx[i] << " " << nx[i+n] << endl;
}
for(int i = 0; i < 2*n; i++) {
// cout << i << " " << nx[i] << endl;
p[i] = -1;
mark[i] = -1;
ordc[i] = -1;
}
for(int i = 0; i < 2*n; i++) {
if(mark[i] == -1) {
dfs(i,i);
}
}
// for(int i = 0; i < 2*n; i++) {
// cout << i << " " << p[i] << " " << disp[i] << endl;
// }
for(int j = 0; j < Q; j++) {
int ans = 0;
for(int i = 0; i < n; i++) {
int k = G[j];
int v = i;
if(P != p[P]) {
if(p[v] == p[P] && k == disp[v]-disp[P])
ans++;
}
else {
if(mark[p[v]] == mark[P] && k >= disp[v] && (ordc[p[v]]+k-disp[v])%szc[mark[p[v]]] == ordc[P])
ans++;
//vai k pra frente de
}
P+= n;
if(P != p[P]) {
if(p[v] == p[P] && k == disp[v]-disp[P])
ans++;
}
else {
if(mark[p[v]] == mark[P] && k >= disp[v] && (ordc[p[v]]+k-disp[v])%szc[mark[p[v]]] == ordc[p[P]])
ans++;
//vai k pra frente de
}
P-= n;
}
answer(ans);
}
}
// int32_t main() {
// ios::sync_with_stdio(false); cin.tie(0);
// freopen("in.in", "r", stdin);
// // freopen("out.out", "w", stdout);
// int N, M, P;
// cin >> N >> M >> P;
// int R[M][2];
// for(int i = 0; i < M; i++) {
// cin >> R[i][0] >> R[i][1];
// }
// int Q; cin >> Q;
// int G[Q];
// for(int i = 0; i < Q; i++) {
// cin >> G[i];
// }
// count_routes(N,M,P,R,Q,G);
// }
