#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
int k, p, res = 0;
vector<bool> vis;
vector<vector<pair<int, int>>> g;
void dfs(int u, int d = 0) {
if (d == k) {
res += (u == p);
return;
}
int mn = 2e5, i = -1;
for (auto [v, w] : g[u]) {
if (vis[v]) continue;
if (w < mn) {
mn = w;
i = v;
}
}
if (i == -1) {
for (auto [v, w] : g[u]) {
if (w < mn) {
mn = w;
i = v;
}
}
}
vis[u] = 1;
dfs(i, d + 1);
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
p = P;
k = G[0];
g.resize(N);
vis.resize(N);
for (int i = 0; i < M; i++) {
int u = R[i][0], v = R[i][1];
g[u].push_back({v, i});
g[v].push_back({u, i});
}
for (int i = 0; i < N; i++) {
fill(vis.begin(), vis.end(), 0);
dfs(i);
}
answer(res);
}
