#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
using ll = long long;
//#define int ll
#define sz(x) (x).size()
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int nmax = 3e5 + 5, inf = 1e9 + 5;
namespace G {
int n;
int target[nmax];
vector<int> trans[nmax];
int isspecial[nmax];
vector<int> lst;
int addnode(int x = 0) {
isspecial[n] = x;
if(x)
lst.emplace_back(n);
return n++;
}
void addedge(int x, int y) { // SIIGUR ESTE FUNCTIONAL
target[x] = y;
trans[y].emplace_back(x);
//cerr << x << " -> " << y << '\n';
}
int flag = 0;
int K[2];
int occ[nmax];
int isoncycle[nmax];
int findcycdim(int node) {
++flag;
if(occ[node] != 0)
return flag - occ[node];
occ[node] = flag;
int rez = findcycdim(target[node]);
if(flag - occ[node] <= rez) isoncycle[node] = 1;
return rez;
}
void findcycdim(int P1, int P2) {
K[0] = findcycdim(P1);
for(int i = 0; i < n; i++)
occ[i] = 0;
flag = 0;
K[1] = findcycdim(P2);
}
int prec[nmax * 2];
void dfs(int node, int *time, int atr = 0) {
queue<int> que;
que.emplace(node);
time[node] = 0;
while(!que.empty()) {
int node = que.front();
//cerr << node << ' ' << occ[node] << ' ' << time[node] << '\n';
que.pop();
if(occ[node] == 1) continue;
occ[node] = 1;
for(auto x : trans[node]) {
if(occ[x] == 0 && time[node] + 1 < time[x]) {
time[x] = time[node] + 1;
que.emplace(x);
}
}
}
return;
}
int time[2][nmax];
int how[2];
void countprec(int P1, int P2) {
for(int i = 0; i < n; i++)
occ[i] = 0, time[0][i] = inf;
for(int i = 0; i < n; i++) time[1][i] = inf;
if(isoncycle[P1])
how[0] = 1;
if(isoncycle[P2])
how[1] = 1;
dfs(P1, time[0], 0);
if(P2 != P1) {
for(int j = 0; j < n; j++)
occ[j] = 0;
dfs(P2, time[1], 0);
}
else
how[1] = 0;
flag = 3;
return;
}
int count(int A) {
flag++;
int cnt = 0;
for(auto i : lst) {
if(time[0][i] == A || (how[0] == 1 && time[0][i] <= A && time[0][i] % K[0] == A % K[0]))
occ[i] = flag, cnt++;
}
for(auto i : lst) {
if(occ[i] == flag) continue;
if(time[1][i] == A || (how[1] == 1 && time[1][i] <= A && time[1][i] % K[1] == A % K[1]))
occ[i] = flag, cnt++;
}
//for(int i = 0; i < n; i++)
//cerr << occ[i] << ' ';
//cerr << '\n';
return cnt;
}
}
vector<pii> g[nmax];
int atr[nmax][2];
pii atre[nmax][2];
void count_routes(int n, int m, int P, int R[][2], int Q, int G[]) {
G::lst.reserve(nmax);
for(int i = 0; i < m; i++) {
g[R[i][0]].emplace_back(R[i][1], m - i);
g[R[i][1]].emplace_back(R[i][0], m - i);
}
for(int i = 0; i < n; i++) {
atr[i][0] = atr[i][1] = -1;
if(sz(g[i]) == 0) continue;
atr[i][0] = atr[i][1] = G::addnode(1);
if(sz(g[i]) == 1) continue;
atr[i][1] = G::addnode();
}
for(int i = 0; i < n; i++) {
//cerr << atr[i][0] << ' ' << atr[i][1] << '\n';
atre[i][0] = atre[i][1] = pii{-1, -1};
for(auto [x, e] : g[i]) {
if(atre[i][0].second < e) {
atre[i][1] = atre[i][0];
atre[i][0] = pii{x, e};
}
else if(atre[i][1].second < e)
atre[i][1] = pii{x, e};
}
}
for(int i = 0; i < n; i++) {
if(sz(g[i]) == 0) continue;
auto [x, e] = atre[i][0];
if(atre[x][0].second == e)
G::addedge(atr[i][0], atr[x][1]);
else
G::addedge(atr[i][0], atr[x][0]);
if(sz(g[i]) == 1) continue;
tie(x, e) = atre[i][1];
if(atre[x][0].second == e)
G::addedge(atr[i][1], atr[x][1]);
else
G::addedge(atr[i][1], atr[x][0]);
}
G::findcycdim(atr[P][0], atr[P][1]);
G::countprec(atr[P][0], atr[P][1]);
for(int i = 0; i < Q; i++) {
answer(G::count(G[i]));
}
return;
}
