#include "garden.h"
#include "gardenlib.h"
//for 69 point;
const int N_ = 150020;
int nxt[N_][2];
int up[N_][2][31][2];
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
int i, j, k;
++P;
for(i=0;i<M;i++)R[i][0]++, R[i][1]++;
for(i=0;i<M;i++){
if(!nxt[R[i][0]][0])nxt[R[i][0]][0] = R[i][1];
else if(!nxt[R[i][0]][1])nxt[R[i][0]][1] = R[i][1];
if(!nxt[R[i][1]][0])nxt[R[i][1]][0] = R[i][0];
else if(!nxt[R[i][1]][1])nxt[R[i][1]][1] = R[i][0];
}
for(i=1;i<=N;i++)
for(j=0;j<2;j++){
up[i][j][0][1] = nxt[i][j];
if(nxt[nxt[i][j]][0] == i && nxt[nxt[i][j]][1])up[i][j][0][0] = 1;
}
for(k=1;k<31;k++)
for(i=1;i<=N;i++)
for(j=0;j<2;j++){
int t = up[i][j][k-1][0];
up[i][j][k][0] = up[up[i][j][k-1][1]][t][k-1][0];
up[i][j][k][1] = up[up[i][j][k-1][1]][t][k-1][1];
}
for(i=0;i<Q;i++){
int cnt = 0;
for(j=1;j<=N;j++){
int now = j, to = 0;
for(int k=30;k>=0;k--){
if(1<<k&G[i]){
int save = now;
now = up[now][to][k][1];
to = up[save][to][k][0];
}
}
if(now == P)cnt++;
}
answer(cnt);
}
}
