#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 150001;
vector<int> adj[N];
int cNum = 1;
int cSize[N][2];
int best[N][2];
int dist[N][2][2];
vector<array<int, 2>> st;
int onCycle[N][2];
int onSt[N][2];
int p;
void dfs(int node, int type)
{
st.push_back({node, type});
onSt[node][type] = 1;
array<int, 2> next = {-1, -1};
int other = -1;
int eVal = -1;
if (type == 0)
{
other = adj[node][0];
eVal = best[node][0];
} else
{
other = adj[node][1];
eVal = best[node][1];
}
if (best[other][0] == eVal && best[other][1] != 0)
{
next = {other, 1};
} else
{
next = {other, 0};
}
if (cSize[next[0]][next[1]])
{
cSize[node][type] = cSize[next[0]][next[1]];
for (int k = 0; k <= 1; k++)
{
if (dist[next[0]][next[1]][k] == -1) dist[node][type][k] = -1;
else dist[node][type][k] = dist[next[0]][next[1]][k] + 1;
}
} else if (onSt[next[0]][next[1]])
{
auto it = st.rbegin();
int siz = 0;
array<int, 2> good = {-1, -1};
int cdist = 0;
//cout << node << " " << type << " " << next[0] << " " << next[1] << endl;
while (*it != next)
{
onCycle[(*it)[0]][(*it)[1]] = 1;
//cout <<(*it)[0] << " " << (*it)[1] << endl;
siz++;
array<int, 2> ar1 = {p, 0};
array<int, 2> ar2 = {p, 1};
if (*it == ar1)
{
good[0] = cdist;
}
if (*it == ar2)
{
good[1] = cdist;
}
cdist++;
it++;
}
onCycle[(*it)[0]][(*it)[1]] = 1;
//cout <<(*it)[0] << " " << (*it)[1] << endl;
siz++;
//cout << "b " << cdist << endl;
for (int k = 0; k <= 1; k++)
{
if (good[k] != -1)
{
dist[node][type][k] = siz - good[k];
}
}
cSize[node][type] = siz;
} else
{
dfs(next[0], next[1]);
cSize[node][type] = cSize[next[0]][next[1]];
for (int k = 0; k <= 1; k++)
{
if (dist[next[0]][next[1]][k] == -1) dist[node][type][k] = -1;
else dist[node][type][k] = dist[next[0]][next[1]][k] + 1;
}
}
if (node == p) dist[node][type][type] = 0;
st.pop_back();
onSt[node][type] = 0;
}
void count_routes(int n, int m, int pa, int R[][2], int Q, int G[])
{
p = pa;
for (int i = 0; i < m; i++)
{
for (int j = 0; j <= 1; j++)
{
if (best[R[i][j]][0] == 0) best[R[i][j]][0] = i + 1;
else if (best[R[i][j]][1] == 0) best[R[i][j]][1] = i + 1;
}
adj[R[i][0]].push_back(R[i][1]);
adj[R[i][1]].push_back(R[i][0]);
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j <= 1; j++) for (int l = 0; l <= 1; l++) dist[i][j][l] = -1;
}
for (int i = 0; i < n; i++)
{
if (!cSize[i][0]) dfs(i, 0);
}
for(int i=0; i<Q; i++)
{
int sum = 0;
int cdist = G[i];
for (int j = 0; j < n; j++)
{
//if (i == 0) cout << "a " << cSize[j][0]<< " " << dist[j][0][0] << " " << dist[j][0][1] << " " << j << endl;
for (int k = 0; k <= 1; k++)
{
if (dist[j][0][k] != -1)
{
if (dist[j][0][k] == cdist) sum++;
else if (onCycle[p][k] && cdist > dist[j][0][k] && dist[j][0][k] % cSize[j][0] == cdist % cSize[j][0])
{
sum++;
}
}
}
}
answer(sum);
}
}
/*
5 4 3
0 1
1 2
2 3
3 4
20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
*/
