import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sa = br.readLine().split(" ");
		int n = Integer.parseInt(sa[0]);
		int m = Integer.parseInt(sa[1]);
		long t = Long.parseLong(sa[2]);
		List<List<Integer>> list = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			list.add(new ArrayList<>());
		}
		for (int i = 0; i < m; i++) {
			sa = br.readLine().split(" ");
			int a = Integer.parseInt(sa[0]);
			int b = Integer.parseInt(sa[1]);
			list.get(a).add(b);
		}
		br.close();

		int e = 63;
		List<List<Set<Integer>>> dp = new ArrayList<>(e);
		List<Set<Integer>> wk = new ArrayList<>(n);
		for (int i = 0; i < n; i++) {
			Set<Integer> set = new HashSet<>();
			set.addAll(list.get(i));
			wk.add(set);
		}
		dp.add(wk);
		for (int i = 1; i < e; i++) {
			wk = new ArrayList<>(n);
			List<Set<Integer>> pre = dp.get(i - 1);
			for (int j = 0; j < n; j++) {
				Set<Integer> set = new HashSet<>();
				Set<Integer> ps = pre.get(j);
				for (int k : ps) {
					set.addAll(pre.get(k));
				}
				wk.add(set);
			}
			dp.add(wk);
		}

		Set<Integer> ans = new HashSet<>();
		ans.add(0);
		for (int i = 0; i < e; i++) {
			if ((t >> i & 1) == 0) {
				continue;
			}
			Set<Integer> set = new HashSet<>();
			List<Set<Integer>> di = dp.get(i);
			for (int j = 0; j < n; j++) {
				for (int k : ans) {
					if (di.get(k).contains(j)) {
						set.add(j);
					}
				}
			}
			ans = set;
		}
		System.out.println(ans.size());
	}
}