#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
vector<vector<int>> graf, auxgraf;
int p, n, m, v1[300005], v2[300005], c, cycle1, cycle2;
void afis()
{
for(int i = 0; i < 2 * n; i++)
{
if(i % 2)
cout << i / 2 << "' : ";
else
cout << i / 2 << " : ";
if(graf[i].size())
{
if(graf[i][0] % 2)
cout << graf[i][0] / 2 << "'";
else
cout << graf[i][0] / 2;
}
cout << '\n';
}
cout << '\n';
}
int dfs1(int node)
{
if(!v1[node])
return 0;
if(v1[node] > 0)
return v1[node];
if(graf[node].size())
{
v1[node] = 0;
v1[node] = dfs1(graf[node][0]);
if(v1[node] > 0)
v1[node]++;
return v1[node];
}
return 0;
}
int dfs2(int node)
{
if(!v2[node])
return 0;
if(v2[node] > 0)
return v2[node];
if(graf[node].size())
{
v2[node] = 0;
v2[node] = dfs2(graf[node][0]);
if(v2[node] > 0)
v2[node]++;
return v2[node];
}
return 0;
}
int dfs3(int nodeStart)
{
int dist = 0, node;
stack<int> s;
s.push(nodeStart);
v1[nodeStart] = 1;
while(!s.empty())
{
node = s.top();
s.pop();
v1[node] = 1;
if(!graf[node].size())
return 0;
if(graf[node][0] == nodeStart)
return dist + 1;
dist++;
if(!v1[graf[node][0]])
s.push(graf[node][0]);
}
return 0;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
p = P;
n = N;
m = M;
graf.resize(2 * N + 1);
auxgraf.resize(N + 1);
for(int i = 0; i < 2 * N; i++)
v2[i] = -1;
for(int i = 0; i < M; i++)
{
if(auxgraf[R[i][0]].size() < 2)
auxgraf[R[i][0]].push_back(R[i][1]);
if(auxgraf[R[i][1]].size() < 2)
auxgraf[R[i][1]].push_back(R[i][0]);
}
for(int i = 0; i < N; i++)
{
if(auxgraf[auxgraf[i][0]][0] == i && auxgraf[auxgraf[i][0]].size() > 1)
graf[2 * i].push_back(2 * auxgraf[i][0] + 1);
else
graf[2 * i].push_back(2 * auxgraf[i][0]);
if(auxgraf[i].size() == 2)
{
if(auxgraf[auxgraf[i][1]][0] == i && auxgraf[auxgraf[i][1]].size() > 1)
graf[2 * i + 1].push_back(2 * auxgraf[i][1] + 1);
else
graf[2 * i + 1].push_back(2 * auxgraf[i][1]);
}
}
//afis();
cycle1 = dfs3(P * 2);
for(int i = 0; i < 2 * N; i++)
v1[i] = 0;
cycle2 = dfs3(P * 2 + 1);
for(int i = 0; i < 2 * N; i++)
v1[i] = -1;
//cout << cycle1 << ' ' << cycle2 << '\n';
v1[P * 2] = 1;
for(int i = 0; i < 2 * N; i++)
{
if(v1[i])
v1[i] = dfs1(i);
}
/* for(int i = 0; i < 2 * N; i++)
{
if(i % 2)
cout << i / 2 << "' " << v1[i] << '\n';
else
cout << i / 2 << " " << v1[i] << '\n';
}
cout << '\n';*/
v2[P * 2 + 1] = 1;
for(int i = 0; i < 2 * N; i++)
{
if(v2[i])
v2[i] = dfs2(i);
}
/* for(int i = 0; i < 2 * N; i++)
{
if(i % 2)
cout << i / 2 << "' " << v2[i] << '\n';
else
cout << i / 2 << " " << v2[i] << '\n';
}*/
for(int i = 0; i < Q; i++)
{
c = 0;
for(int j = 0; j < 2 * N; j += 2)
{
if(v1[j] > 0 && !cycle1 && G[i] - v1[j] + 1 == 0)
c++;
else if(v2[j] > 0 && !cycle2 && G[i] - v2[j] + 1 == 0)
c++;
else if(G[i] - v2[j] + 1 >= 0 && v1[j] > 0 && cycle1 && (G[i] - v1[j] + 1) % cycle1 == 0)
c++;
else if(G[i] - v2[j] + 1 >= 0 && v2[j] > 0 && cycle2 && (G[i] - v2[j] + 1) % cycle2 == 0)
c++;
}
answer(c);
}
}
