/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <ctype.h>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin (),v.end()
using namespace std;
#ifndef death
#include "garden.h"
#include "gardenlib.h"
#endif
#ifdef death
void answer(int x)
{
cout<<"! "<<x<<endl;
}
#endif
int n,m,p,q,c[2003];
LL dp[2*150005][32];
int dir[2*150005],nxt[2*150005][32];
vector<pair<int,int>> g[150005];
void addNode(int a,int b)
{
dir[a]=b;
//cout<<a<<" "<<b<<endl;
}
void count_routes(int N,int M,int P,int R[][2] ,int Q,int K[])
{
n=N;
m=M;
q=Q;
p=P+1;
for(int i=0;i<m;i++)
{
int a=R[i][0]+1,b=R[i][1]+1;
g[a].PB(MP(i,b));
g[b].PB(MP(i,a));
}
for(int i=1;i<=q;i++)
c[i]=K[i-1];
for(int i=1;i<=n;i++)
sort(all(g[i]));
for(int i=1;i<=n;i++)
{
int to;
if(g[i].empty())
continue;
to=g[i][0].second;
if(i==g[to][0].second)
addNode(i,n+to);
else
addNode(i,to);
if(g[i].size()==1)
to=g[i][0].second;
else
to=g[i][1].second;
if(i==g[to][0].second)
addNode(i+n,to+n);
else
addNode(i+n,to);
}
for(int i=1;i<=2*n;i++)
nxt[i][0]=dir[i];
for(int j=1;j<29;j++)
for(int i=1;i<=2*n;i++)
nxt[i][j]=nxt[nxt[i][j-1]][j-1];
for(int k=1;k<=q;k++)
{
int K=c[k];
vector<int> s;
for(int j=0;j<=29;j++)
{
if(K%2)
s.PB(j);
K/=2;
}
for(int i=1;i<=2*n;i++)
for(int j=0;j<=29;j++)
dp[i][j]=0;
for(int i=1;i<=n;i++)
dp[nxt[i][s[0]]][0]++;
for(int j=1;j<s.size();j++)
for(int i=1;i<=2*n;i++)
dp[ nxt[i][s[j]] ][j]+=dp[i][j-1];
answer(dp[p][s.size()-1]+dp[p+n][s.size()-1]);
}
}
#ifdef death
int main()
{
int N,M,Q,P,R[102][2],K[102];
cin>>N>>M>>P;
for(int i=0;i<M;i++)
cin>>R[i][0]>>R[i][1];
cin>>Q;
for(int i=0;i<Q;i++)
cin>>K[i];
count_routes(N,M,P,R,Q,K);
return 0;
}
#endif
/*
2 1 0
0 1
1
1
*/
