#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
vector <vector <int>> adj;
int n, m, p, q;
int ans = 0;
void solve(int cnt, int p, int u) {
if (cnt == q && u != p) {
return;
}
else if (cnt == q && u == p) {
ans++;
return;
}
if (adj[u].size() == 1) {
solve(cnt + 1, u, adj[u][0]);
}
else {
solve(cnt + 1, u, adj[u][1]);
}
return;
}
void count_routes(int N, int M, int P, int r[][2], int Q, int g[]) {
n = N;
adj.resize(n);
m = M;
p = P;
for (int i = 0;i < m;i++) {
int u = r[i][0];
int v = r[i][1];
if (adj[u].size() < 2) adj[u].push_back(v);
if (adj[v].size() < 2) adj[v].push_back(u);
}
for(int i = 0; i < Q; i++) {
q = g[i];
int ans = 0;
for (int i = 0;i < n;i++) {
solve(0, -1, i);
}
answer(ans);
}
}
/*int main() {
int r[6][2];
r[0][0] = 1;
r[0][1] = 2;
r[1][0] = 0;
r[1][1] = 1;
r[2][0] = 0;
r[2][1] = 3;
r[3][0] = 3;
r[3][1] = 4;
r[4][0] = 4;
r[4][1] = 5;
r[5][0] = 1;
r[5][1] = 5;
int q[1];
q[0] = 3;
cout << count_routes(6, 6, 0, r, 1, q);
}
*/
