#include "garden.h"
#include "gardenlib.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>>adj;
bool valid=false;
void dfs(int node,int prv,int k,int p)
{
if(k==0)
{
valid=(node==p);
return;
}
if(adj[node].size()==1)
dfs(adj[node][0],node,k-1,p);
else
{
if(prv==adj[node][0])
dfs(adj[node][1],node,k-1,p);
else
dfs(adj[node][0],node,k-1,p);
}
}
void count_routes(int n, int m, int p, int r[][2], int q, int g[])
{
adj.resize(n+1);
for(int i=0; i<n; i++)
{
adj[r[i][0]].push_back(r[i][1]);
adj[r[i][1]].push_back(r[i][0]);
}
int ans=0;
for(int i=0;i<n;i++)
{
valid=false;
dfs(i,-1,g[0],p);
ans+=valid;
}
answer(ans);
}
