#include using namespace std; const int MAX = 50000; int main(){ int N, M; long long T; cin >> N >> M >> T; vector> E(N); for (int i = 0; i < M; i++){ int a, b; cin >> a >> b; E[a].push_back(b); } vector> dp(MAX + 1, vector(N, false)); dp[0][0] = true; vector> p(N); for (int i = 0; i < MAX; i++){ for (int j = 0; j < N; j++){ if (dp[i][j]){ p[j].push_back(i); for (int k : E[j]){ dp[i + 1][k] = true; } } } } int ans = 0; if (T <= MAX){ for (int i = 0; i < N; i++){ if (dp[T][i]){ ans++; } } } else { for (int i = 0; i < N; i++){ if (p[i].size() >= 2){ int a = p[i][p[i].size() - 2]; int b = p[i][p[i].size() - 1]; int d = b - a; if (b + d >= MAX){ if (T % d == a % d){ ans++; } } } } } cout << ans << endl; }