#pragma GCC optimize("Ofast")
#include "garden.h"
#include "gardenlib.h"
#include <vector>
#include <iostream>
using namespace std;
struct graph
{
int n;
int h;
vector<vector<int>> adjlist;
vector<vector<int>> best;
vector<int> dist;
vector<bool> cycle;
int cyc = 2e9;
int p;
void add(int fr, int to)
{
int t = to;
if (fr == best[to][0]) t += h;
if (best[fr][0] == to)
{
adjlist[fr].push_back(t);
}
if (best[fr][1] == to)
{
adjlist[fr + h].push_back(t);
}
}
graph(int in, int m, vector<vector<int>> ib, int R[][2]) : n(2*in), h(in), adjlist(vector<vector<int>>(2*n)), best(ib), dist(n, -1), cycle(n)
{
for (int i = 0; i < m; i++)
{
add(R[i][0], R[i][1]);
add(R[i][1], R[i][0]);
}
}
void print()
{
cout << n << "\n";
for (int i = 0; i < n; i++)
{
for (auto j : adjlist[i])
{
cout << i << " " << j << "\n";
}
}
}
void reverse()
{
vector<vector<int>> old(n);
swap(old, adjlist);
for (int i = 0; i < n; i++)
{
for (int j : old[i])
{
adjlist[j].push_back(i);
}
}
}
bool dfs(int curr, int d)
{
if (curr == p && dist[curr] != -1)
{
cyc = d;
return true;
}
dist[curr] = d;
for (auto next : adjlist[curr])
{
if (dfs(next, d + 1)) cycle[curr] = true;
}
return cycle[curr];
}
void calc(int P)
{
p = P;
dfs(p, 0);
}
void pcyc()
{
cout << "Cycle: " << cyc << "\n";
for (int i = 0; i < n; i++)
{
cout << (i % h);
if (i >= h) cout << "*";
else cout << " ";
cout << ": ";
cout << cycle[i] << " " << dist[i] << "\n";
}
}
bool check(int v, int t)
{
if (t < dist[v]) return false;
if (t % cyc != dist[v] % cyc) return false;
return true;
}
};
void count_routes(int n, int m, int P, int R[][2], int Q, int G[])
{
vector<vector<int>> best(n, vector<int>(2, -1));
auto ins = [&](int k, int v)
{
swap(best[k][0], best[k][1]);
best[k][0] = v;
};
for (int i = m - 1; i >= 0; i--)
{
ins(R[i][0], R[i][1]);
ins(R[i][1], R[i][0]);
}
for (int i = 0; i < n; i++) if (best[i][1] == -1) best[i][1] = best[i][0];
graph g(n, m, best, R);
g.reverse();
graph g2(g);
g.calc(P);
g2.calc(P + n);
for (int c = 0; c < Q; c++)
{
int v = G[c];
int r = 0;
for (int i = 0; i < n; i++)
{
r += g.check(i, v);
r += g2.check(i, v);
}
answer(r);
}
}
