#include // #include using namespace std; // using namespace atcoder; using ll = long long; using ull = unsigned long long; using P = pair; #define rep(i,n) for(ll i = 0;i < (ll)n;i++) #define ALL(x) (x).begin(),(x).end() #define MOD 1000000007 // 2020/12/31 void matrix_mul(vector> &v,vector> &w){ int n = v.size(),m = w[0].size(),l = w.size(); vector> res(n,vector(m)); for(int i = 0;i < n;i++)for(int j = 0;j < m;j++){ bool k = 0; for(int g = 0;g < l;g++)k |= (v[i][g] && w[g][j]); res[i][j] = k; } swap(res,v); } //正方行列のみだよ void matrix_pow(vector> &v,ll K){ int n = v.size(); vector> res(n,vector(n,1)); while(K){ if(K & 1)matrix_mul(res,v); matrix_mul(v,v); K >>= 1; } swap(res,v); } int main(){ ll n,m,T; cin >> n >> m >> T; vector> v(n,vector(n,0)); rep(i,m){ int a,b;cin >> a >> b; v[b][a] = 1; } matrix_pow(v,T); vector> res(n,vector(1,0)); res[0][0] = 1; matrix_mul(v,res); int ans = 0; rep(i,n)if(v[i][0])ans++; cout << ans << "\n"; return 0; }