#include<bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,L[150009],P,msh[150009][32],msh2[150009][32],MSH[150009][32],MSH2[150009][32],K,pas;
vector <pair <int, int> > VP[150009];
void count_routes(int NN, int MM, int PP, int RR[][2], int QQ, int GG[])
{
a=NN;b=MM;P=PP+1;tes=QQ;
for(i=1; i<=a; i++){
L[i]=b+5;
}
for(i=1; i<=b; i++){
c=RR[i-1][0]+1;d=RR[i-1][1]+1;
L[c]=min(L[c],i);L[d]=min(L[d],i);
VP[c].push_back({i,d});VP[d].push_back({i,c});
}
for(i=1; i<=a; i++){
sort(VP[i].begin(),VP[i].end());
msh[i][0]=VP[i][0].second;MSH[i][0]=VP[i][0].first;
if(VP[i].size()==1){
msh2[i][0]=msh[i][0];MSH2[i][0]=MSH[i][0];
}else{
msh2[i][0]=VP[i][1].second;MSH2[i][0]=VP[i][1].first;
}
}
for(j=1; j<=30; j++){
for(i=1; i<=a; i++){
c=msh[i][j-1];d=MSH[i][j-1];
if(L[c]!=d){
msh[i][j]=msh[c][j-1];
MSH[i][j]=MSH[c][j-1];
}else{
msh[i][j]=msh2[c][j-1];
MSH[i][j]=MSH2[c][j-1];
}
c=msh2[i][j-1];d=MSH2[i][j-1];
if(L[c]!=d){
msh2[i][j]=msh[c][j-1];
MSH2[i][j]=MSH[c][j-1];
}else{
msh2[i][j]=msh2[c][j-1];
MSH2[i][j]=MSH2[c][j-1];
}
}
}
K=GG[0];
pas=0;
for(i=1; i<=a; i++){
c=i;d=-2;
for(j=0; j<=30; j++){
if((K&(1<<j))==0) continue;
if(L[c]!=d){
zx=msh[c][j];xc=MSH[c][j];
}else{
zx=msh2[c][j];xc=MSH2[c][j];
}
c=zx;d=xc;
}
//cout<<i<<" I "<<c<<"\n";
if(c==P){
pas++;
}
}
//cout<<"pasuxi: "<<pas<<"\n";
answer(pas);
}
