n, m, t = map(int, input().split())
A = [[False] * n for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    A[b][a] = True
def mul(a, b):
    return [[any(a[i][k] and b[k][j] for k in range(n)) for j in range(n)] for i in range(n)]
now = [[i == j for j in range(n)] for i in range(n)]
while t:
    if t & 1:
        now = mul(now, A)
    t >>= 1
    A = mul(A, A)
ans = sum(now[i][0] for i in range(n))
print(ans)