#define rep(i,n) for(int i=0;i<(int)(n);i++) #define ALL(v) v.begin(),v.end() typedef long long ll; #include using namespace std; vector> matrixmul(ll m,vector> a,vector> b){ vector> c(m,vector(m,0)); rep(i,m){ rep(j,m){ rep(k,m) c[i][j]=c[i][j]|(a[i][k]&b[k][j]); } } return c; } vector> matrixpow(ll m,vector> vec,ll n){ vector> ans(m,vector(m,0)); rep(i,m) ans[i][i]=1; while(n){ if(n&1) ans=matrixmul(m,ans,vec); vec=matrixmul(m,vec,vec); n>>=1; } return ans; } int main(){ int n,m; ll t; cin>>n>>m>>t; vector> A(n,vector (n)); rep(i,m){ int a,b; cin>>a>>b; A[b][a]=1; } vector> B=matrixpow(n,A,t); int ans=0; rep(i,n){ if(B[i][0]==1) ans++; } cout<