#include <bits/stdc++.h>
#include "gardenlib.h"
//#include "grader.h"
using namespace std;
#define S second
#define F first
#define LL long long
const int N1 = 2e5+10;
const LL MOD = 1e9+7;
const LL LINF = 1e18;
const LL INF = 1e9;
map<pair<int,int>,int>nxt;
vector<pair<int,int>>adj[N1];
map<pair<int,int>,int>mp;
map<int,pair<int,int>>mp1;
int cnt = 0;
int compress(int a,int b){
if(mp.find({a,b})!=mp.end())
return mp[{a,b}];
else
return mp1[cnt] = make_pair(a,b),mp[{a,b}] = cnt++;
}
pair<int,int> uncompress(int val){
return mp1[val];
}
int get_after(int i,int k){
int pre = INF;
for(int j=30;j>=0;j--)
if((1<<j)>k)continue;
else {
LL val = nxt[{compress(i,pre),j}];
pair<int,int>p = uncompress(val);
i = p.F,pre = p.S;
k -= 1<<j;
}
return i;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
int n = N;
for(int i=0;i<M;i++){
adj[R[i][0]].push_back({i,R[i][1]});
adj[R[i][1]].push_back({i,R[i][0]});
}
for(int i=0;i<n;i++){
set<pair<int,int>>st;
for(auto x:adj[i])
st.insert(x);
nxt[{compress(i,INF),0}] = compress((*st.begin()).S,(*st.begin()).F);
//printf("%d %d %d\n",i,nxt[{{i,INF},0}].F,nxt[{{i,INF},0}].S);
for(auto x:adj[i]){
st.erase(x);
if(!st.empty()){
pair<int,int>p = *st.begin();
nxt[{compress(i,x.F),0}] = compress(p.S,p.F);
}
else
nxt[{compress(i,x.F),0}] = compress(x.S,x.F);
//printf("%d %d 0 %d %d\n",i,x.F,nxt[{{i,x.F},0}].F,nxt[{{i,x.F},0}].S);
st.insert(x);
}
}
for(int j=1;j<=30;j++)
for(int i=0;i<n;i++){
LL val = compress(i,INF);
nxt[{val,j}] = nxt[{nxt[{val,j-1}],j-1}];
for(auto x:adj[i]){
LL val = compress(i,x.F);
LL val1 = nxt[{val,j-1}];
nxt[{val,j}] = nxt[{val1,j-1}];
//printf("%d %d %d %d %d\n",i,x.S,j,nxt[{{i,x.S},j}].F,nxt[{{i,x.S},j}].S);
continue;
}
}
for(int i=0;i<Q;i++){
int ans1 = 0;
for(int j=0;j<n;j++){
if(get_after(j,G[i])==P)ans1++;
//printf("%d %d\n",j,get_after(j,G[i]));
}
answer(ans1);
}
}
/*
#define MAX_M 1000000
#define MAX_Q 2000
static int N, M, P, Q;
static int R[MAX_M][2];
static int G[MAX_Q];
static int solutions[MAX_Q];
static int answers[MAX_Q];
static int answer_count;
inline
void my_assert(int e) {if (!e) abort();}
void read_input()
{
int i;
my_assert(3==scanf("%d %d %d",&N,&M,&P));
for(i=0; i<M; i++)
my_assert(2==scanf("%d %d",&R[i][0],&R[i][1]));
my_assert(1==scanf("%d",&Q));
for(i=0; i<Q; i++)
my_assert(1==scanf("%d",&G[i]));
for(i=0; i<Q; i++)
my_assert(1==scanf("%d",&solutions[i]));
}
void answer(int x)
{
if(answer_count>=Q) {
printf("Incorrect. Too many answers.\n");
exit(0);
}
answers[answer_count] = x;
answer_count++;
}
int main()
{
int correct, i;
read_input();
answer_count = 0;
count_routes(N,M,P,R,Q,G);
if(answer_count!=Q) {
printf("Incorrect. Too few answers.\n");
exit(0);
}
correct = 1;
for(i=0; i<Q; i++)
if(answers[i]!=solutions[i])
correct = 0;
if(correct)
printf("Correct.\n");
else {
printf("Incorrect.\n");
printf("Expected: ");
for(i=0; i<Q; i++)
printf("%d ",solutions[i]);
printf("\nReturned: ");
for(i=0; i<Q; i++)
printf("%d ",answers[i]);
}
return 0;
}
*/
