#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
void count_routes(int n, int m, int p, int r[][2], int q, int g[]){
const int lg = 32;
vector<vector<int>> ed(n, vector<int>(2, -1));
for (int i = 0; i < m; ++i) {
if (ed[r[i][0]][0] == -1) ed[r[i][0]][0] = r[i][1];
else if (ed[r[i][0]][1] == -1) ed[r[i][0]][1] = r[i][1];
if (ed[r[i][1]][0] == -1) ed[r[i][1]][0] = r[i][0];
else if (ed[r[i][1]][1] == -1) ed[r[i][1]][1] = r[i][0];
}
for (int i = 0; i < n; ++i) {
if (ed[i][1] == -1) ed[i][1] = ed[i][0];
}
vector<vector<int>> gg(2*n);
for (int i = 0; i < n; ++i){
int t1 = ed[i][0];
if (ed[t1][0] == i) gg[i].push_back(t1 + n);
else gg[i].push_back(t1);
int t2 = ed[i][1];
if (ed[t2][0] == i) gg[i + n].push_back(t2 + n);
else gg[i + n].push_back(t2);
}
vector<vector<int>> up(2*n, vector<int>(lg));
for (int i = 0; i < 2*n; ++i) up[i][0] = gg[i][0];
for (int i = 1; i < lg; ++i){
for (int j = 0; j < 2*n; ++j){
up[j][i] = up[up[j][i-1]][i-1];
}
}
int ans = 0;
for (int i = 0; i < n; ++i){
int cur = i;
int k = g[0];
int x = 0;
while (k > 0){
if (k % 2) cur = up[cur][x];
x++; k /= 2;
}
if (cur == p || cur == p + n) ans++;
}
answer(ans);
}
