#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = std::int_fast64_t;
using std::cout;
using std::cerr;
using std::endl;
using std::cin;

template<typename T> std::vector<T> make_v(size_t a, T b){return std::vector<T>(a, b);}
template<typename... Ts> auto make_v(size_t a, Ts... ts){
  return std::vector<decltype(make_v(ts...))>(a, make_v(ts...));
}
template<typename T> std::vector<T> make_v(size_t a){return std::vector<T>(a);}
template<typename T, typename... Ts> auto make_v(size_t a, Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template<class T, std::uint_fast32_t& N>
class square_matrix {
public:
	using value_type = T;
	using reference = value_type &;
	using const_reference = const reference;
	using size_type = std::uint_fast32_t;
	using container = std::vector<value_type>;
	using matrix = std::vector<container>;

	using u64 = std::uint_fast64_t;

protected:
	matrix data;

public:
	constexpr square_matrix(const square_matrix &) = default;
	constexpr square_matrix(square_matrix &&) = default;

	constexpr square_matrix() : data(N, std::vector<value_type>(N)){}
	constexpr square_matrix(matrix & data) : data(data) {}

	constexpr square_matrix & operator=(const square_matrix &) = default;
	constexpr square_matrix & operator=(square_matrix &&) = default;

	constexpr static const square_matrix E() {
		square_matrix e;
		for(int i = 0; i < N; i++) e[i][i] = 1;
		return e;
	}
	constexpr static const square_matrix O() {
		return square_matrix();
	}

	const square_matrix pow(const u64 & k) {
		return (*this) ^ k;
	}
	const T determinant() const {
		square_matrix B(*this);
		T ret = 1;
		for(int i = 0; i < width(); i++) {
			int ind = -1;
			for(int j = i; j < width(); j++) {
				if(B[j][i] == 0) continue;
				ind = j;
			}
			if(ind == -1) return 0;
			if(i != ind) {
				ret *= -1;
				std::swap(B[i], B[ind]);
			}

			ret *= B[i][i];
			for(int j = 0; j < width(); j++) B[i][j] /= B[i][i];
			for(int j = i + 1; j < width(); j++)
				for(int k = 0; k < width(); k++)
					B[j][k] -= B[i][k] * B[j][i];
		}
		return ret;
	}

	constexpr const size_type size() const { return N; }
	constexpr const size_type height() const { return N; }
	constexpr const size_type width() const { return N; }
	const std::vector<value_type> & operator[](const size_type & k) const { return data.at(k); }
	std::vector<value_type> & operator[](const size_type & k) { return data.at(k); }
	const matrix get_data() { return data; }
	void swap(square_matrix & r) { data.swap(r.data); }

	square_matrix & operator+=(const square_matrix & B) {
		for(int i = 0; i < height(); i++)
			for(int j = 0; j < width(); j++)
				(*this)[i][j] += B[i][j];
		return (*this);
	}
	square_matrix & operator-=(const square_matrix & B) {
		for(int i = 0; i < height(); i++)
			for(int j = 0; j < width(); j++)
				(*this)[i][j] -= B[i][j];
		return (*this);
	}
	square_matrix & operator*=(const square_matrix & B) {
		auto C = square_matrix::O();
		for(int i = 0; i < height(); i++)
			for(int j = 0; j < width(); j++)
				for(int k = 0; k < height(); k++)
					C[i][j] = (C[i][j] + (*this)[i][k] * B[k][j]);
		return (*this) = C;
	}
	square_matrix & operator^=(u64 k) {
		auto B = square_matrix::E();
		while(k) {
			if(k & 1) B *= (*this);
			(*this) *= (*this);
			k >>= 1;
		}
		return (*this) = B;
	}
	const square_matrix operator+(const square_matrix & B) const {
		return (square_matrix(*this) += B);
	}
	const square_matrix operator-(const square_matrix & B) const {
		return (square_matrix(*this) -= B);
	}
	const square_matrix operator*(const square_matrix & B) const {
		return (square_matrix(*this) *= B);
	}
	const square_matrix operator^(const u64 & k) const {
		return (square_matrix(*this) ^= k);
	}
	const bool operator==(const square_matrix & B) const {
		return (data == B.data);
	}
	friend std::ostream & operator<<(std::ostream & os, square_matrix & p) {
		for(int i = 0; i < height(); i++) {
			os << "[";
			for(int j = 0; j < width(); j++) {
				os << p[i][j] << (j + 1 == width() ? "]\n" : ", ");
			}
		}
		return os;
	}
};

std::uint_fast32_t n;

int main() {
  int m, t; scanf("%u%d%d", &n, &m, &t);
  square_matrix<bool, n> g;
  for(int i = 0; i < m; i++) {
    int a, b; scanf("%d%d", &a, &b);
    g[a][b] = true;
  }
  g ^= t;

  int ans = 0;
  for(int i = 0; i < n; i++) if(g[0][i]) ans++;
  printf("%d\n", ans);
	return 0;
}