/** made by amunduzbaev **/
#include "garden.h"
#include "gardenlib.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define fastios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define Pi acos(-1);
#define mod 1e9+7
#define inf 1e18
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<int> vii;
typedef vector<pll> vpll;
typedef vector<pii> vpii;
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}
const int NN = 2e3+5;
const int B = 10;
vpii edges[NN];
int K, used[NN];
ll cnt, goal;
void check(int u, int k, int p){
int mn = mod, go = -1;
if(k == K){
if(u == goal) cnt++;
return;
}
if(sz(edges[u]) == 1 && p != -1) { check(p, k+1, u); return; }
for(auto x:edges[u]){
if(p == x.ff) continue;
if(x.ss < mn){
mn = x.ss;
go = x.ff;
}
}
check(go, k+1, u);
}
void count_routes(int n, int m, int p, int R[][2], int q, int kk[]){
//cout<<"\n";
for(int i=0; i<m; i++){
edges[R[i][0]].pb({R[i][1], i});
edges[R[i][1]].pb({R[i][0], i});
}
goal = p;
for(int i=0;i<q;i++){
memset(used, 0, sizeof used);
K = kk[i];
queue<pii> qq;
qq.push({0, p});
while(!qq.empty()){
pii cur = qq.front(); qq.pop();
if(cur.ff < K){
for(auto x:edges[cur.ss]){
if(used[x.ff]) continue;
used[x.ff] = 1;
qq.push({cur.ff+1, x.ff});
}
}
check(cur.ss, 0, -1);
}
answer(cnt);
cnt = 0;
}
}
/*
6 6 0
1 2
0 1
0 3
3 4
4 5
1 5
1
3
2
5 5 2
1 0
1 2
3 2
1 3
4 2
2
3 1
1 2
*/
