#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <iterator>
using namespace std;
void answer(int x);
const int MAXN = 150000;
const int MAXN2 = MAXN * 2;
int arr[MAXN2 + 10];
int dis[2][MAXN2 + 10];
bool chk[2][MAXN2 + 10];
void f(int x, int p)
{
chk[p % 2][x] = 1;
if(arr[x] == p)
{
dis[p % 2][x] = 1;
return;
}
if(!chk[p % 2][arr[x]])
f(arr[x], p);
if(dis[p % 2][arr[x]])
dis[p % 2][x] = dis[p % 2][arr[x]] + 1;
}
int mem1[MAXN + 10];
int mem2[MAXN + 10];
int sum[2][MAXN2 + 10];
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
memset(mem1, -1, sizeof mem1);
memset(mem2, -1, sizeof mem2);
memset(arr, -1, sizeof arr);
for(int i = 0; i < M; i++)
{
int x = R[i][0];
int y = R[i][1];
if(mem1[x] == -1)
mem1[x] = y;
else if(mem2[x] == -1)
mem2[x] = y;
if(mem1[y] == -1)
mem1[y] = x;
else if(mem2[y] == -1)
mem2[y] = x;
}
for(int i = 0; i < N; i++)
{
if(mem1[mem1[i]] == i && mem2[mem1[i]] != -1)
arr[2 * i] = 2 * mem1[i] + 1;
else
arr[2 * i] = 2 * mem1[i];
if(mem2[i] != -1)
{
if(mem1[mem2[i]] == i && mem2[mem2[i]] != -1)
arr[2 * i + 1] = 2 * mem2[i] + 1;
else
arr[2 * i + 1] = 2 * mem2[i];
}
}
for(int r = 0; r < 2; r++)
for(int i = 0; i < 2 * N; i++)
if(!chk[r][i] && arr[i] != -1)
f(i, 2 * P + r);
for(int r = 0; r < 2; r++)
for(int i = 0; i < N; i++)
if(dis[r][2 * i])
sum[r][dis[r][2 * i]]++;
for(int r = 0; r < 2; r++)
{
int c = dis[r][2 * P + r];
if(!c)
continue;
for(int i = 1; i <= 2 * N; i++)
if(i - c >= 1)
sum[r][i] += sum[r][i - c];
}
int c[2] = { dis[0][2 * P], dis[1][2 * P + 1] };
if(!c[0])
c[0] = c[1];
if(!c[1])
c[1] = c[0];
for(int i = 0; i < Q; i++)
{
int ans = 0;
for(int r=0;r<2;r++)
{
int t = G[i];
if(t > 2 * N && c[r])
t -= ((t - 2 * N + c[r] - 1) / c[r]) * c[r];
if(t <= 2 * N)
ans += sum[r][t];
}
answer(ans);
}
}
