//In the name of God
#include "garden.h"
#include "gardenlib.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll maxn = 5e5 + 100;
const ll mod = 1e9 + 7;
const ll INF = 1e18;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
ll pw(ll a, ll b){
ll c = 1;
while(b){
if(b & 1) c = c * a % mod;
a = a * a % mod;
b >>= 1;
}
return c;
}
int n, a[maxn], dis[maxn];
int cnt[2][maxn], dor[2];
bool vis[maxn];
vector<int> g[maxn], gp[maxn];
void dfs(int v){
vis[v] = 1;
for(int u : gp[v]){
if(vis[u]) continue;
dis[u] = dis[v] + 1;
dfs(u);
}
return;
}
void Do(int x, int f){
memset(dis, -1, sizeof dis);
memset(vis, 0, sizeof vis);
dis[x] = 0;
dfs(x);
for(int i = 0; i < (n << 1); i += 2){
if(~dis[i]) cnt[f][dis[i]]++;
}
dor[f] = -1;
if(dis[a[x]] == -1) return;
int t = dis[a[x]] + 1;
dor[f] = t;
for(int i = t; i < maxn; i++){
cnt[f][i] += cnt[f][i - t];
}
return;
}
void count_routes(int N, int m, int p, int R[][2], int Q, int G[]){
n = N;
for(int i = 0; i < m; i++){
int v = R[i][0], u = R[i][1];
g[v].pb(u);
g[u].pb(v);
}
for(int i = 0; i < n; i++){
int v = g[i][0];
if(g[v][0] == i) a[i << 1] = (v << 1) | 1;
else a[i << 1] = v << 1;
if(Sz(g[i]) == 1){
a[i << 1 | 1] = a[i << 1];
continue;
}
v = g[i][1];
if(g[v][0] == i) a[i << 1 | 1] = (v << 1) | 1;
else a[i << 1 | 1] = v << 1;
}
for(int i = 0; i < (n << 1); i++){
gp[a[i]].pb(i);
}
Do(p << 1, 0);
Do(p << 1 | 1, 1);
for(int i = 0; i < Q; i++){
int x = G[i];
int ans = 0;
if(dor[0] == -1){
if(x < maxn) ans += cnt[0][x];
}
else{
while(x >= maxn) x -= dor[0];
ans += cnt[0][x];
}
x = G[i];
if(dor[1] == -1){
if(x < maxn) ans += cnt[1][x];
}
else{
while(x >= maxn) x -= dor[1];
ans += cnt[1][x];
}
answer(ans);
}
return;
}
