#include using namespace std; typedef long long int ll; typedef pair P; typedef vector VI; typedef vector VVI; #define REP(i,n) for(int i=0;i<(n);i++) #define ALL(v) v.begin(),v.end() constexpr ll MOD=1000000007; constexpr ll INF=1e18; VVI edge(110,VI(0)); int main(){ int n, m; cin >> n >> m; ll t; cin >> t; int a, b; bool f[110][110]={0}; REP(i,m){ cin >> a >> b; f[a][b]=1; } REP(i,n)REP(j,n){ if(f[i][j]) edge[i].push_back(j); } queue

q; q.push({0,0}); map mp; mp[{0,0}]=1; while(!q.empty()){ P p=q.front(); if(p.second>=11000) break; q.pop(); for(auto to:edge[p.first]){ if(!mp[{to,p.second+1}]){ mp[{to,p.second+1}]=1; q.push({to,p.second+1}); } } } if(t<11000){ int ans=0; REP(i,n) ans+=mp[{i,t}]; cout << ans << endl; } else{ int ans=0; REP(i,n){ int x=-1; for(int j=10000;j<10200;j++){ if(mp[{i,j}]){ if(x!=-1){ if(t%(j-x)==x%(j-x)) ans++; break; } x=j; } } } cout << ans << endl; } return 0; }