#include "garden.h"
#include "gardenlib.h"
#include<algorithm>
#include<string.h>
using namespace std;
int sw,sx,sp,x,y,top,w,n,m,p,con[300010][2],cnt,g[300010],q,d[300010][2],leng[300010][2],ch[300010][2],dap[2010];
struct data2{
int x,p;
}sav[300010];
struct data{
int x,y,c;
bool operator<(const data&r)const
{
if(x==r.x) return c<r.c;
return x<r.x;
}
}arr[300010];
void dfs(int x,int k)
{
int i;
if(ch[x][k]==cnt){sw=1; sx=x; sp=k; return;}
if(ch[x][k]!=cnt && ch[x][k]!=0){sw=2; sx=x; sp=k; return;}
ch[x][k]=cnt;
top++; sav[top].x=x; sav[top].p=k;
if(con[con[x][k]][1]==0) dfs(con[x][k],0);
else if(con[con[x][k]][0]==x) dfs(con[x][k],1);
else dfs(con[x][k],0);
}
void put(int t)
{
int i,j,k,c=0;
if(sw==1){
for(i=1;i<=top;i++) if(sav[i].x==p && sav[i].p==t) break;
if(i==top+1) return;
for(j=1;j<=top;j++) if(sav[j].x==sx && sav[j].p==sp) break;
if(i>=j){
for(k=i-1;k!=i;k--){
if(k==j-1) k=top;
d[sav[k].x][sav[k].p]=++c;
leng[sav[k].x][sav[k].p]=top-i+1;
}
leng[p][t]=top-i+1;
}
else{
for(k=i-1;k>=1;k--) d[sav[k].x][sav[k].p]=++c;
}
}
else{
if(!(sx==p && sp==t) && d[sx][sp]==0) return;
for(i=top;i>=1;i--){
c++;
d[sav[i].x][sav[i].p]=d[sx][sp]+c;
leng[sav[i].x][sav[i].p]=leng[sx][sp];
}
}
}
void query()
{
int i,j,k;
top=0; cnt++; dfs(p,0); put(0);
for(i=1;i<=n;i++){
top=0; cnt++; dfs(i,0); put(0);
top=0; cnt++; dfs(i,1); put(0);
}
for(k=1;k<=2;k++){
for(i=1;i<=q;i++){
for(j=1;j<=n;j++){
if(leng[j][0]==0 && d[j][0]==g[i]) dap[i]++;
if(leng[j][0]!=0 && d[j][0]<=g[i] && (g[i]-d[j][0])%leng[j][0]==0) dap[i]++;
}
}
cnt=0; memset(d,0,sizeof d); memset(leng,0,sizeof leng); memset(ch,0,sizeof ch); memset(sav,0,sizeof sav);
top=0; cnt++; dfs(p,1); put(1);
for(i=1;i<=n;i++){
top=0; cnt++; dfs(i,0); put(1);
top=0; cnt++; dfs(i,1); put(1);
}
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
int i;
n=N; m=M; p=P+1; q=Q;
for(i=1;i<=m;i++)
{
x=R[i-1][0]+1; y=R[i-1][1]+1;
w++; arr[w].x=x; arr[w].y=y; arr[w].c=i;
w++; arr[w].x=y; arr[w].y=x; arr[w].c=i;
}
for(i=1;i<=q;i++) g[i]=G[i-1];
sort(arr+1,arr+w+1);
for(i=1;i<=w;i++){
if(arr[i].x!=arr[i-1].x){
con[arr[i].x][0]=arr[i].y;
if(arr[i].x==arr[i+1].x) con[arr[i].x][1]=arr[i+1].y;
}
}
query();
for(i=1; i<=Q; i++)
answer(dap[i]);
}
