#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
const int MAXN = 3e5 + 10;
vector<pair<int, int>> edges[MAXN];
vector<int> adj[MAXN][2];
int dist[MAXN][2];
int marc[MAXN], comp[MAXN];
int sz[MAXN], deg[MAXN];
void dfs_1(int v, int x){
marc[v] = 1;
for(auto u : adj[v][1]){
if(!marc[u]){
dist[u][x] = dist[v][x] + 1;
dfs_1(u, x);
}
}
}
void dfs_2(int v, int c){
comp[v] = c;
sz[c] ++;
for(auto u : adj[v][0]){
if(deg[u] == 0) continue;
if(!comp[u]) dfs_2(u, c);
}
}
void lenhadora(int n){
queue<int> q;
for(int i=0; i<(2 * n); i++){
if(deg[i] == 0){
q.push(i);
}
}
while(!q.empty()){
int v = q.front();
q.pop();
for(auto u : adj[v][0]){
deg[u] --;
if(deg[u] == 0) q.push(u);
}
}
}
void count_routes(int n, int m, int p, int r[][2], int q, int g[]){
for(int i=0; i<(2 * n); i++){
marc[i] = comp[i] = 0;
dist[i][0] = dist[i][1] = -1;
adj[i][0].clear();
adj[i][1].clear();
}
for(int i=0; i<m; i++){
edges[r[i][0]].push_back({i, r[i][1]});
edges[r[i][1]].push_back({i, r[i][0]});
}
for(int i=0; i<n; i++) sort(edges[i].begin(), edges[i].end());
for(int i=0; i<n; i++){
for(int k=0; k<2; k++){
int x = 0;
if(k == 1 && edges[i].size() == 1) x = 1;
auto [e, j] = edges[i][(x ? 0 : k)];
if(e != edges[j][0].first){
adj[i + k * n][0].push_back(j);
adj[j][1].push_back(i + k * n);
deg[j] ++;
} else{
adj[i + k * n][0].push_back(j + n);
adj[j + n][1].push_back(i + k * n);
deg[j + n] ++;
}
}
}
dist[p][0] = 0;
dfs_1(p, 0);
for(int i=0; i<(2 * n); i++) marc[i] = 0;
dist[p + n][1] = 0;
dfs_1(p + n, 1);
lenhadora(n);
int c = 0;
for(int i=0; i<(2 * n); i++){
if(deg[i] == 0) continue;
if(!comp[i]) dfs_2(i, ++c);
}
for(int i=0; i<q; i++){
int cnt = 0;
for(int j=0; j<n; j++){
bool ok = false;
for(int k=0; k<2; k++){
if(dist[j][k] == -1) continue;
int sz_c = sz[comp[p + k * n]];
if(sz_c == 0){
ok |= (dist[j][k] == g[i]);
} else if(dist[j][k] <= g[i]) ok |= ((g[i] - dist[j][k]) % sz_c == 0);
}
cnt += ok;
}
answer(cnt);
}
}
