#include "garden.h"
#include "gardenlib.h"
#include "bits/stdc++.h"
using namespace std;
const int MX = 150005;
int k;
int PP;
int ans;
stack<int> stk;
int vis[MX][2];
vector<int> g[MX];
void Dfs (int v, int p, int t) {
//cout << v << ' ';
if (t == k && v == PP) {
ans++;
//cout << "GG";
return;
}
if (t > k) return;
int nx = (g[v].size() == 1 ? 0 : (p == g[v][0]));
Dfs(g[v][nx], v, t + 1);
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
PP = P;
for (int i = 0; i < M; ++i) {
g[R[i][0]].push_back(R[i][1]);
g[R[i][1]].push_back(R[i][0]);
}
k = G[0];
for (int i = 0; i < N; ++i) {
Dfs(i, -1, 0);
//cout << '\n';
}
answer(ans);
}
