#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
vector <vector <int>> adj;
int n, m, goal, q;
int ans = 0;
void solve(int cnt, int p, int u) {
// cout << cnt << " " << p << " " << u << " " << goal << endl;
if (cnt == q && u != goal) {
return;
}
else if (cnt == q && u == goal) {
ans++;
return;
}
for (auto v : adj[u]) {
if (v == p && adj[u].size() == 2) continue;
solve(cnt + 1, u, v);
break;
}
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;
goal = 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;
count_routes(6, 6, 0, r, 1, q);
cout << ans << endl;
*/
