#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pair<int,int>> vpi;
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define rsz resize
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define fi first
#define se second
int const n=15e4+3;
vpi adj[n];
int nxt[n][2];
vpi pre[n][2];
int d[n][2];
void dfs(int now,bool f,int w)
{
if(d[now][f]!=-1)return;
d[now][f]=w;
trav(e,pre[now][f])
{
dfs(e.fi,e.se,w+1);
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
F0R(i,M)
{
int u = R[i][0];
int v = R[i][1];
adj[u].pb({M-i,v});
adj[v].pb({M-i,u});
}
F0R(i,N)
{
sort(all(adj[i]));
reverse(all(adj[i]));
nxt[i][0]=adj[i][0].se;
nxt[i][1]=adj[i][0].se;
if(sz(adj[i])>1)
{
nxt[i][1]=adj[i][1].se;
}
}
F0R(i,N)
{
if(nxt[nxt[i][0]][0]==i)
{
pre[nxt[i][0]][1].pb({i,0});
}
else
{
pre[nxt[i][0]][0].pb({i,0});
}
if(nxt[nxt[i][1]][0]==i)
{
pre[nxt[i][1]][1].pb({i,1});
}
else
{
pre[nxt[i][1]][0].pb({i,1});
}
}
F0R(i,N)
{
d[i][0]=d[i][1]=-1;
}
dfs(P,0,0);
dfs(P,1,0);
if(nxt[P][0]==P)
{
d[P][0]=d[nxt[P][0]][1]+1;
}
else
{
d[P][0]=d[nxt[P][0]][0]+1;
}
if(nxt[P][1]==P)
{
d[P][1]=d[nxt[P][1]][1]+1;
}
else
{
d[P][1]=d[nxt[P][1]][0]+1;
}
F0R(j,Q)
{
int ans=0;
F0R(i,N)
{
if(d[i][0]!=-1 && G[j]%d[i][0]==0)
{
++ans;
}
}
answer(ans);
}
}
