#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define loop(x, i) for (int i = 0; i < x; i++)
#define pb push_back
// position within the cycle, -1 if not in the cycle
vi pos;
// distance to the cycle
vi dis;
// index of last parent *not* in cycle
vi entryPoint;
vi component, cycleLengths;
vvi revrs;
vvi p;
int getNthParent(int x, int k)
{
loop(30, i)
{
if ((1 << i) & k)
x = p[i][x];
}
return x;
}
int getDis(int a, int b)
{
if (component[a] != component[b])
return -1;
int res = 0;
if (pos[a] == -1)
{
if (pos[a] == pos[b])
{
if (entryPoint[a] == entryPoint[b] && dis[a] >= dis[b])
{
int k = dis[a] - dis[b];
if (getNthParent(a, k) == b)
return k;
return -1;
}
return -1;
}
res += dis[a];
a = p[0][entryPoint[a]];
}
if (pos[b] == -1)
{
return -1;
}
if (component[a] != component[b])
throw;
int cycleLength = cycleLengths[component[a]];
res += (pos[b] - pos[a] + cycleLength) % cycleLength;
return res;
}
void cycleNumbering(int i, int nr)
{
if (pos[i] != -1)
{
cycleLengths.pb(nr);
return;
}
pos[i] = nr;
cycleNumbering(p[0][i], nr + 1);
}
void revDFS(int i, int c)
{
component[i] = c;
for (int j : revrs[i])
{
if (component[j] == -1)
{
revDFS(j, c);
}
}
}
void DFS(int i, int c)
{
if (component[i] != -1)
{
cycleNumbering(i, 0);
return;
}
revDFS(i, c);
DFS(p[0][i], c);
}
ii getEntryPoint(int i)
{
if (entryPoint[i] != -1)
return {entryPoint[i], dis[i]};
if (pos[p[0][i]] != -1)
{
dis[i] = 1;
entryPoint[i] = i;
return {i, 1};
}
auto [j, d] = getEntryPoint(p[0][i]);
entryPoint[i] = j;
dis[i] = d + 1;
return {j, d + 1};
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
vvi adj(N);
loop(M, i)
{
adj[R[i][0]].pb(R[i][1]);
adj[R[i][1]].pb(R[i][0]);
}
p = vvi(30, vi(2 * N));
loop(N, i)
{
int j = adj[i][0];
if (adj[j][0] == i)
j += N;
p[0][i] = j;
if (adj[i].size() == 1)
{
p[0][i + N] = j;
}
else
{
j = adj[i][1];
if (adj[j][0] == i)
j += N;
p[0][i + N] = j;
}
}
for (int x = 1; x < 30; x++)
{
loop(2 * N, i)
{
int half = p[x - 1][i];
p[x][i] = p[x - 1][half];
}
}
pos = dis = entryPoint = component = vi(2 * N, -1);
revrs = vvi(2 * N);
loop(2 * N, i)
{
revrs[p[0][i]].pb(i);
}
int c = 0;
loop(2 * N, i)
{
if (component[i] == -1)
{
DFS(i, c);
c++;
}
}
loop(2 * N, i)
{
if (pos[i] == -1 && entryPoint[i] == -1)
{
getEntryPoint(i);
}
}
for (int i = 0; i < Q; i++)
{
int K = G[i];
int cnt = 0;
loop(N, start)
{
auto reachesGoal = [&](int goal) -> bool
{
if (component[start] != component[goal])
return 0;
if (pos[goal] >= 0)
{
int l = cycleLengths[component[goal]];
if (pos[start] >= 0)
{
return ((pos[goal] - pos[start] + l) % l) == (K % l);
}
else
{
int d = dis[start];
if (d > K)
return 0;
int cur = p[0][entryPoint[start]];
return ((pos[goal] - pos[cur] + l) % l) == ((K - d) % l);
}
}
else if (entryPoint[start] == entryPoint[goal])
{
if (dis[start] == dis[goal] + K)
{
// check with euler tour
if (getNthParent(start, K) == goal)
return 1; // not always...
}
}
return 0;
};
if (reachesGoal(P) || reachesGoal(P + N))
cnt++;
// if (nthParent(start, K) % N == P) cnt++;
}
answer(cnt);
}
}
