#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
struct Node
{
vector<Node*> n;
};
Node *P;
vector<Node> nodes;
int traverse(Node *t, Node *p, int c)
{
if(c==0) return t==P;
if(t->n[0]==p && t->n.size()>1) return traverse(t->n[1],t,c-1);
return traverse(t->n[0],t,c-1);
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
// setup graph
nodes.resize(N);
for(int i = 0; i < M; i++)
{
nodes[R[i][0]].n.push_back(&nodes[R[i][1]]);
nodes[R[i][1]].n.push_back(&nodes[R[i][0]]);
}
::P = &nodes[P];
for(int i = 0; i < Q; i++)
{
int c = 0;
for(int j = 0; j < N; j++) c += traverse(&nodes[j],nullptr,G[i]);
answer(c);
}
}
