#include "garden.h"
#include "gardenlib.h"
#define pb push_back
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
int n, m, p;
vector < pair < int, int > > g[maxn];
int ans = 0, steps;
void dfs(int beg, int from, int depth)
{
//cout << beg << " " << from << " w " << depth << endl;
if(beg == p && depth == steps)
{
ans ++;
return;
}
if(depth > steps)return;
int madeit = 0;
for (auto &[nb, index]: g[beg])
{
if(nb == from)continue;
if(madeit)break;
madeit = 1;
dfs(nb, beg, depth+1);
}
if(!madeit)dfs(from, beg, depth+1);
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
n = N;
m = M;
p = P;
for (int i = 0; i < m; ++ i)
{
int from = R[i][0];
int to = R[i][1];
g[from].pb({to, i});
g[to].pb({from, i});
}
int i;
for(i=0; i<Q; i++)
{
steps = G[i];
for (int i = 0; i < n; ++ i)
{
dfs(i, -1, 0);
}
answer(ans);
}
}
