#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; int N, M, T; Mat Mul(const Mat& A, const Mat& B){ Mat C(N, Vec(N)); for(int i = 0; i < N; ++i){ for(int k = 0; k < N; ++k){ for(int j = 0; j < N; ++j){ C[i][j] |= A[i][k] & B[k][j]; } } } return C; } Mat Pow(Mat A, ll n){ Mat B(N, Vec(N)); for(int i = 0; i < N; ++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); cin >> N >> M >> T; vector> g(N, vector(N)); for(int i = 0; i < M; ++i){ int a, b; cin >> a >> b; g[a][b] = 1; } g = Pow(g, T); int ans = 0; for(int i = 0; i < N; ++i) ans += g[0][i]; cout << ans << endl; return 0; }