#include "garden.h"
#include "gardenlib.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <climits>
#include <cstring>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using ii = pair<int,int>;
using vii = vector<pair<int,int>>;
using vb = vector<bool>;
template<typename T>
using Graph = vector<vector<T>>;
struct Node
{
int v, i;
bool operator< (const Node& a) const
{
return i < a.i;
}
};
const int MXN = 150000;
int n, p;
int dp[MXN + 5][2];
bool instack[MXN + 5][2];
Graph<Node> graph;
int cycle_length()
{
Graph<bool> visited(n, vb(2, 0));
int steps = 0, u = p, t = 0;
do
{
visited[u][t] = 1;
if(t == 0)
{
int v = graph[u][0].v;
if(graph[v][0].i == graph[u][0].i) t = 1;
else t = 0;
u = graph[u][0].v;
} else
{
int v = graph[u][1].v;
if(graph[v][0].i == graph[u][1].i) t = 1;
else t = 0;
u = graph[u][1].v;
}
++steps;
} while(!visited[u][t] && u != p);
if(u == p) return steps;
return -1;
}
int steps(int u, int i)
{
if(u == p) return 0;
if(instack[u][i])
{
return -2;
}
instack[u][i] = 1;
int& r = dp[u][i];
if(r != -1) return r;
r = 0;
if(i == 0 || graph[u].size() == 1)
{
int v = graph[u][0].v;
int select = 0;
if(graph[v][0].i == graph[u][0].i) select = 1;
int c = steps(graph[u][0].v, select);
if(c == -2) r = -2;
else r = 1 + c;
} else
{
int v = graph[u][1].v;
int select = 0;
if(graph[v][0].i == graph[u][1].i) select = 1;
int c = steps(graph[u][1].v, select);
if(c == -2) r = -2;
else r = 1 + c;
}
instack[u][i] = 0;
return r;
}
// self loops ?
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
n = N;
p = P;
memset(dp, -1, sizeof dp);
graph.assign(N, vector<Node>());
for(int i = 0; i < M; ++i)
{
graph[R[i][0]].push_back(Node { R[i][1], i });
graph[R[i][1]].push_back(Node { R[i][0], i });
}
for(auto x: graph) sort(x.begin(), x.end());
// two cycle lengths
int cycleLength = cycle_length();
for(int j = 0; j < Q; ++j)
{
int r = 0;
for(int i = 0; i < N; ++i)
{
if(i == p)
{
if(cycleLength == G[j]) ++r;
continue;
}
int s = steps(i, 0);
if(s != -2 && s <= G[j])
{
int left = (G[j] - s) % G[j];
if(left == 0) ++r;
else if(cycleLength != -1 && cycleLength == left) ++r;
}
}
answer(r);
}
}
