#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
vector <pair <int, int>> dgraf[1000005];
int parent[1000005];
vector <int> graf[1000005];
bool resenje[1000005];
bool cmp(pair <int, int> a, pair <int, int> b){
return a.second < b.second;
}
int n, m, p, q;
int depth[1000005][2];
int cycle_size[1000005];
bool visited[1000005][2];
void dfs(int v, int koji){
visited[v][koji] = 1;
for(auto c : graf[v]){
if(visited[c][koji]){
int x = v;
queue <int> q;
while(x != c){
q.push(x);
x = parent[x];
if(x == c) break;
}
q.push(c);
int g = q.size();
while(!q.empty()){
cycle_size[q.front()] = g;
q.pop();
}
}
else{
depth[c][koji] = depth[v][koji] + 1;
dfs(c, koji);
}
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
n = N, m = M, p = P, q = Q;
for(int i=0; i<m; i++){
dgraf[R[i][0]].push_back({R[i][1], i});
dgraf[R[i][1]].push_back({R[i][0], i});
}
for(int i=0; i<n; i++){
sort(dgraf[i].begin(), dgraf[i].end(), cmp);
}
for(int i=0; i<n; i++){
if(dgraf[i].size() == 1){
if(dgraf[dgraf[i][0].first][0].first == i){
parent[i] = dgraf[i][0].first + n;
parent[i+n] = dgraf[i][0].first + n;
}
else{
parent[i] = dgraf[i][0].first;
parent[i+n] = dgraf[i][0].first;
}
}
else{
if(dgraf[dgraf[i][0].first][0].first == i) parent[i] = dgraf[i][0].first + n;
else parent[i] = dgraf[i][0].first;
if(dgraf[dgraf[i][1].first][0].first == i) parent[i+n] = dgraf[i][1].first + n;
else parent[i+n] = dgraf[i][1].first;
}
}
for(int i=0; i<2*n; i++){
graf[parent[i]].push_back(i);
}
for(int i=0; i<2*n; i++){
depth[i][0] = depth[i][1] = -1;
}
depth[p][0] = 0;
dfs(p, 0);
depth[p+n][1] = 0;
dfs(p+n, 1);
for(int query=0; query<q; query++){
int k = G[query];
int cnt = 0;
for(int i=0; i<n; i++) resenje[i] = 0;
for(int i=0; i<n; i++){
if(depth[i][0] == -1) continue;
if(depth[i][0] == k){
resenje[i] = 1;
}
else if(cycle_size[p]){
if(k > depth[i][0] && (k-depth[i][0])%cycle_size[p] == 0){
resenje[i] = 1;
//cout << i << " e1 " << endl;
}
}
}
for(int i=0; i<n; i++){
if(depth[i][1] == -1) continue;
if(depth[i][1] == k){
resenje[i] = 1;
}
else if(cycle_size[p+n]){
if(k > depth[i][1] && (k-depth[i][1])%cycle_size[p+n] == 0){
resenje[i] = 1;
}
}
}
for(int i=0; i<n; i++){
cnt += resenje[i];
}
answer(cnt);
}
return;
}
