#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
#define fin cin
#define fout cout
//ifstream fin("x.in"); ofstream fout("x.out");
typedef long long i64;
const int nmax = 15e4 + 5;
const int mmax = 2 * 15e4 + nmax + 5;
const int qmax = 2000;
const pair<int, int> nul = {-1, -1};
static vector<int> c[mmax + 1];
static pair<int, int> pe_ciclu[mmax + 1];
static int reprezentant[mmax + 1], h[mmax + 1];
static bool finalok[mmax + 1];
static vector<int> g[mmax + 1], gt[mmax + 1];
static vector<pair<int, int>> gorig[nmax + 1];
static int top, stk[mmax + 1];
static vector<pair<int, int>> qry[mmax + 1];
static int rasp[qmax + 1];
bool cmp (pair<int, int> a, pair<int, int> b) {
return a.second < b.second;
}
int best (int nod, int indm) {
if (gorig[nod].size() == 1)
return gorig[nod][0].second;
if (gorig[nod][0].second / 2 != indm / 2)
return gorig[nod][0].second;
else
return gorig[nod][1].second;
}
void fa_graf (int N, int &M, int P, int R[][2], int Q, int G[]) {
for (int i = 0; i < M; ++ i) {
gorig[R[i][0]].push_back({R[i][1], 2 * i});
gorig[R[i][1]].push_back({R[i][0], 2 * i + 1});
if (R[i][1] == P)
finalok[2 * i] = 1;
if (R[i][0] == P)
finalok[2 * i + 1] = 1;
}
for (int i = 0; i < N; ++ i) {
sort(gorig[i].begin(), gorig[i].end(), cmp);
}
// muchiile de functie
for (int i = 0; i < M; ++ i) {
int find_edge = best(R[i][1], 2 * i);
g[2 * i].push_back(find_edge);
find_edge = best(R[i][0], 2 * i + 1);
g[2 * i + 1].push_back(find_edge);
}
// 0 ... 2M - 1 sunt muchiile
// 2M... 2M + N - 1 sunt nodurile de start
// adauga noduri suplimentare de start
for (int i = 0; i < N; ++ i) {
if (gorig[i].size())
g[2 * M + i].push_back(gorig[i][0].second);
}
M *= 2;
}
void ciclu (int nod, int tata, int ind) {
c[ind].push_back(nod);
pe_ciclu[nod] = {ind, c[ind].size() - 1};
for (auto i : g[nod]) {
if (pe_ciclu[i] != nul && pe_ciclu[i].first != ind) {
ciclu(i, nod, ind);
}
}
}
int cauta_ciclii (int N) {
// sortare topologica ca sa scot arborii
vector<int> grad(N, 0);
for (int i = 0; i < N; ++ i) {
for (auto j : g[i])
++ grad[j];
}
queue<int> q;
for (int i = 0; i < N; ++ i) {
if (grad[i] == 0)
q.push(i);
}
while (!q.empty()) {
int x = q.front();
q.pop();
pe_ciclu[x] = {-1, -1};
for (auto i : g[x]) {
-- grad[i];
if (grad[i] == 0)
q.push(i);
}
}
// determin care sunt ciclii
int cycles = 0;
for (int i = 0; i < N; ++ i) {
if (pe_ciclu[i] != nul && pe_ciclu[i].first == 0) {
++ cycles;
ciclu(i, -1, cycles);
}
}
return cycles;
}
void dfs (int nod, int tata) {
for (auto i : gt[nod]) {
if (pe_ciclu[i] == nul && i != tata) {
reprezentant[i] = reprezentant[nod];
h[i] = h[nod] + 1;
dfs(i, nod);
}
}
}
void det_arbori (int N, int cnt) {
for (int i = 0; i < N; ++ i) {
for (auto j : g[i]) {
gt[j].push_back(i);
}
}
for (int u = 1; u <= cnt; ++ u) {
for (auto i : c[u]) {
reprezentant[i] = i;
dfs(i, -1);
}
}
}
void solve (int nod, int tata) {
stk[top ++] = nod;
for (auto i : qry[nod]) {
rasp[i.second] += finalok[stk[i.first]];
}
for (auto i : gt[nod]) {
if (pe_ciclu[i] == nul && i != tata) {
solve(i, nod);
}
}
-- top;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
fa_graf(N, M, P, R, Q, G);
int cnt = cauta_ciclii(M + N);
det_arbori(M + N, cnt);
for (int j = M; j < M + N; ++ j) {
for (int i = 0; i < Q; ++ i) {
// pot ajunge de la j in g[i] pasi la o muchie care da in nodul P?
if (G[i] >= h[j]) { // intru pe ciclu
pair<int, int> pos = pe_ciclu[reprezentant[j]];
int final_node = c[pos.first][(pos.second + G[i] - h[j]) % c[pos.first].size()];
if (finalok[final_node] == 1)
++ rasp[i];
} else { // tre sa ridic j cu G[i]
qry[j].push_back({h[j] - G[i], i});
}
}
}
for (int i = 1; i <= cnt; ++ i) {
for (auto j : c[i]) {
solve(j, -1);
}
}
for(int i = 0; i < Q; i ++)
answer(rasp[i]);
}
