//IOI 2011 Day 1 Problem 1 Garden
// First subtask solution 49 points
#include "garden.h"//for CMS
#include "gardenlib.h"//for CMS
//#include "grader.h" // for Yandex
#include <bits/stdc++.h>
using namespace std;
const int inf=1e3+9;
int ans=0,target;
vector<pair<int,int> > v[inf];
void dfs(int node,int left,int par){
if(left==0 ){
ans+=(node==target);
return ;
}
pair<int,int > temp[4];
temp[1]=temp[2]=temp[0]=make_pair(1e9,1e9);
for(auto o:v[node])
temp[2]=o,sort(temp,temp+3);
if(temp[0].second!=par || temp[1].second>=1e9)
dfs(temp[0].second,left-1,node);
else
dfs(temp[1].second,left-1,node);
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
for(int i=0;i<M;i++)
v[R[i][0]].push_back(make_pair(i,R[i][1])),
v[R[i][1]].push_back(make_pair(i,R[i][0]) );
target=P;
for(int i=0;i<N;i++)
dfs(i,G[0],-1);
answer(ans);
}
