import numpy as np
INF = 10 ** 18 + 1
n, m, t = map(int, input().split())
mat = np.full((n, n), INF)
for _ in range(m):
    a, b = map(int, input().split())
    mat[a][b] = 1
res = np.full((n, n), INF)
for i in range(n):
    res[i][i] = 0
while t > 0:
    if t & 1:
        tmp = np.full((n, n), INF)
        for i in range(n):
            for j in range(n):
                tmp[i, j] = (res[i] + mat[:, j]).min()
        res = tmp[:]
    tmp = np.full((n, n), INF)
    for i in range(n):
        for j in range(n):
            tmp[i, j] = (mat[i] + mat[:, j]).min()
    mat = tmp[:]
    t //= 2
ans = 0
for i in range(n):
    if res[0, i] < INF:
        ans += 1
print(ans)