N, M, T = map(int, input().split()) goto = [[set() for j in range(N)] for i in range(60)] for i in range(N): goto[0][i].add(i) for i in range(M): a, b = map(int, input().split()) goto[1][a].add(b) for i in range(2, 60): for j in range(N): goto[i][j] = set() for g in goto[i - 1][j]: goto[i][j] |= goto[i - 1][g] ans = set([0]) for i in range(60): if T >> i & 1: nex = set() for g in ans: nex |= goto[i + 1][g] ans = nex print(len(ans))