def oi(): return int(input()) def os(): return input() def mi(): return list(map(int, input().split())) # import sys # input = sys.stdin.readline # import sys # sys.setrecursionlimit(10**8) # import pypyjit # pypyjit.set_param('max_unroll_recursion=-1') input_count = 0 def prod_func(a,b): return a*b def add_func(a,b): return a+b class MATRIX: def __init__(self, prod_func, add_func): self.prod_func = prod_func self.add_func = add_func def dot(self, A,B): if len(A[0]) != len(B): return None out = [] for ay in range(len(A)): temp = [] for bx in range(len(B[0])): sums = 0 for ax in range(len(A[0])): sums += self.prod_func(A[ay][ax], B[ax][bx]) temp.append(sums) out.append(temp) return out def sum(self, A,B): if not(len(A) == len(B) and len(A[0]) == len(B[0])): return None out = [] for ay in range(len(A)): temp = [] for ax in range(len(A[0])): temp.append(self.add_func(A[ay][ax], B[ay][ax])) out.append(temp) return out def prod(self, A,B): if not(len(A) == len(B) and len(A[0]) == len(B[0])): return None out = [] for ay in range(len(A)): temp = [] for ax in range(len(A[0])): temp.append(self.prod_func(A[ay][ax], B[ay][ax])) out.append(temp) return out # 正方行列AをN乗する。 def ruijou(self, A, N): out = [[0] * len(A) for _ in range(len(A))] for i in range(len(A)): out[i][i] = 1 for i in list(bin(N)[2:][::-1]): if i=="1": out = self.dot(out, A) A = self.dot(A,A) return out input_count = 0 N,M,T = mi() mat = [[0] * N for _ in range(N)] MAT = MATRIX(prod_func, add_func) for i in range(M): a,b = mi() mat[a][b] = 1 out = MAT.ruijou(mat, T) count = 0 for o in out[0]: if o>0: count += 1 print(count)