#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; constexpr int INF = 1001001001; constexpr int mod = 1000000007; // constexpr int mod = 998244353; template inline bool chmax(T& x, T y){ if(x < y){ x = y; return true; } return false; } template inline bool chmin(T& x, T y){ if(x > y){ x = y; return true; } return false; } using Vec = vector; using Mat = vector; Mat Mul(const Mat& A, const Mat& B){ Mat C(A.size(), Vec(B.size())); for(int i = 0; i < (int)A.size(); ++i){ for(int k = 0; k < (int)A[i].size(); ++k){ for(int j = 0; j < (int)B.size(); ++j){ C[i][j] |= A[i][k] & B[k][j]; } } } return C; } Mat Pow(Mat A, ll n){ Mat B(A.size(), Vec(A.size())); for(int i = 0; i < (int)A.size(); ++i) B[i][i] = 1; while(n > 0){ if(n & 1) B = Mul(B, A); A = Mul(A, A); n >>= 1; } return B; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N, M, T; cin >> N >> M >> T; vector> g(N, vector(N)); vector outdeg(N); for(int i = 0; i < M; ++i){ int a, b; cin >> a >> b; g[a][b] = 1; outdeg[a] += 1; } g = Pow(g, T + 1); int ans = 0; for(int i = 0; i < N; ++i) ans += g[0][i] & (outdeg[i] > 0); cout << ans << endl; return 0; }