#include "game.h"

#define NDEBUG

#include <bits/stdc++.h>
using namespace std;

#pragma region debug

#ifndef NDEBUG
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
	return os << '(' << p.first << ", " << p.second << ')';
}

template<typename T1, typename T2, typename T3>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3> &p) {
	return os << '(' << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ')';
}

template<typename T1, typename T2, typename T3, typename T4>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3, T4> &p) {
	return os << '(' << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ", " << get<3>(p) << ')';
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
	os << '[';
	if (v.size()) {
		os << *v.begin();
		for (auto i = next(v.begin()); i != v.end(); i++)
		os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const deque<T> &d) {
	os << '[';
	if (d.size()) {
		os << *d.begin();
		for (auto i = next(d.begin()); i != d.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, stack<T> s) {
	os << '[';
	if (s.size()) {
		int n = s.size();
		vector<T> v(n);
		for (int i = 0; i < n; i++) {
			v[i] = s.top();
			s.pop();
		}
		os << v[n - 1];
		for (int i = n - 2; i >= 0; i--) 
			os << ", " << v[i];
		}
	return os << "]>";
}

template<typename T>
ostream &operator<<(ostream &os, queue<T> q) {
	os << '[';
	if (q.size()) {
		int n = q.size();
		vector<T> v(n);
		for (int i = 0; i < n; i++) {
			v[i] = q.front();
			q.pop();
		}
		os << v[n - 1];
		for (int i = n - 2; i >= 0; i--) 
			os << ", " << v[i];
	}
	return os << "]>";
}

template<typename T, size_t N>
ostream &operator<<(ostream &os, const array<T, N> &a) {
	os << '[';
	if (N) {
		os << *a.begin();
		for (auto i = next(a.begin()); i != a.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const set<T> &s) {
	os << '[';
	if (s.size()) {
		os << *s.begin();
		for (auto i = next(s.begin()); i != s.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const unordered_set<T> &s) {
	os << '[';
	if (s.size()) {
		os << *s.begin();
		for (auto i = next(s.begin()); i != s.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const multiset<T> &s) {
	os << '[';
	if (s.size()) {
		os << *s.begin();
		for (auto i = next(s.begin()); i != s.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T1, typename T2>
ostream &operator<<(ostream &os, const map<T1, T2> &m) {
	os << '[';
	if (m.size()) {
		os << '(' << m.begin()->first << " : " << m.begin()->second << ')';
		for (auto i = next(m.begin()); i != m.end(); i++)
			os << ", " << '(' << i->first << " : " << i->second << ')';
	}
	return os << ']';
}

template<typename T1, typename T2>
ostream& operator<<(ostream& os, const unordered_map<T1, T2> &m) {
	os << '[';
	if (m.size()) {
		os << '(' << m.begin()->first << " : " << m.begin()->second << ')';
		for (auto i = next(m.begin()); i != m.end(); i++)
			os << ", " << '(' << i->first << " : " << i->second << ')';
	}
	return os << ']';
}

map<char, string> _dbg_dict {
	{'1', "--------------------------------"},
	{'2', "================================"},
	{'3', "≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡"},
	{'4', "################################"},
	{'*', "********************************"},
	{'_', "_"},
	{'<', "<!---- "},
	{'>', " ----!>"},
	{'(', "(!==== "},
	{')', "==== !)"},
	{'[', "[!≡≡≡≡ "},
	{']', " ≡≡≡≡!]"},
	{'{', "{!#### "},
	{'}', " ####!}"},
	{'c', "checkpoint "},
	{'l', "line "},
	{'n', "\n"},
	{'t', "\t"}
};

template<typename T>
void _dbg_print(string var, const T &a) { cerr << var << " = " << a << '\n'; }

void _dbg_print(string var, const char *a) {
	int n = strlen(a);
	for (int i = 0; i < n; i++) 
 cerr << (i < n - 1 && a[i] == '_' && _dbg_dict.find(a[i + 1]) != _dbg_dict.end() ? _dbg_dict[a[++i]] : string(1, a[i]));
}

#define dbg1(a) _dbg_print(#a, a);
#define dbg2(a, b) dbg1(a) dbg1(b)
#define dbg3(a, b, c) dbg1(a) dbg2(b, c)
#define dbg4(a, b, c, d) dbg1(a) dbg3(b, c, d)
#define dbg5(a, b, c, d, e) dbg1(a) dbg4(b, c, d, e)
#define dbg6(a, b, c, d, e, f) dbg1(a) dbg5(b, c, d, e, f)
#define dbg7(a, b, c, d, e, f, g) dbg1(a) dbg6(b, c, d, e, f, g)
#define dbg8(a, b, c, d, e, f, g, h) dbg1(a) dbg7(b, c, d, e, f, g, h)
#define dbg9(a, b, c, d, e, f, g, h, i) dbg1(a) dbg8(b, c, d, e, f, g, h, i)
#define dbg10(a, b, c, d, e, f, g, h, i, j) dbg1(a) dbg9(b, c, d, e, f, g, h, i, j)
#define dbg11(a, b, c, d, e, f, g, h, i, j, k) dbg1(a) dbg10(b, c, d, e, f, g, h, i, j, k)
#define dbg12(a, b, c, d, e, f, g, h, i, j, k, l) dbg1(a) dbg11(b, c, d, e, f, g, h, i, j, k, l)
#define dbg13(a, b, c, d, e, f, g, h, i, j, k, l, m) dbg1(a) dbg12(b, c, d, e, f, g, h, i, j, k, l, m)
#define dbg14(a, b, c, d, e, f, g, h, i, j, k, l, m, n) dbg1(a) dbg13(b, c, d, e, f, g, h, i, j, k, l, m, n)
#define dbg15(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o) dbg1(a) dbg14(b, c, d, e, f, g, h, i, j, k, l, m, n, o)
#define dbg16(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p) dbg1(a) dbg15(b, c, d, e, f, g, h, i, j, k, l, m, n, o, p)
#define get_dbg(_1, _2, _3, _4, _5, _6, _7, _8, _9, _10, _11, _12, _13, _14, _15, _16, NAME, ...) NAME
#define dbg(...) get_dbg(__VA_ARGS__, dbg16, dbg15, dbg14, dbg13, dbg12, dbg11, dbg10, dbg9, dbg8, \
	dbg7, dbg6, dbg5, dbg4, dbg3, dbg2, dbg1)(__VA_ARGS__)
#else
#define dbg(...)
#endif

#pragma endregion debug

#pragma region y_combinator

#ifndef Y_COMBINATOR_HPP
#define Y_COMBINATOR_HPP

template<class Fun>
class y_combinator_result {
	Fun fun_;
public:
	template<class T>
	explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}

	template<class ...Args>
	decltype(auto) operator()(Args &&...args) {
		return fun_(std::ref(*this), std::forward<Args>(args)...);
	}
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
	return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

#endif

#pragma endregion y_combinator

namespace game {
	int N, K;
	vector<int> A, B;
	vector<vector<int>> G, H;

	void init_slow(int _N, int _K) {
		N = _N;
		K = _K;
		A.assign(N, INT_MAX);
		iota(A.begin(), A.begin() + K, 0);
		B.assign(N, INT_MIN);
		iota(B.begin(), B.begin() + K, 0);
		G.resize(N);
		H.resize(N);
	}	

	bool add_teleporter_slow(int s, int t) {
		if (s < K && t < K)
			return t <= s;
		G[s].push_back(t);
		H[t].push_back(s);
		
		auto dfsa = y_combinator([&](auto dfsa, int u, int k) -> bool {
			if (A[u] <= k)
				return false;
			A[u] = k;
			if (A[u] <= B[u])
				return true;
			for (int v : H[u])
				if (dfsa(v, k))
					return true;
			return false;
		});

		auto dfsb = y_combinator([&](auto dfsb, int u, int k) -> bool {
			if (k <= B[u])
				return false;
			B[u] = k;
			if (A[u] <= B[u])
				return true;
			for (int v : G[u])
				if (dfsb(v, k))
					return true;
			return false;
		});

		return dfsa(s, A[t]) || dfsb(t, B[s]);
	}

	const int S = 100;

	vector<int> C, D;

	void init_fast(int _N, int _K) {
		N = _N;
		K = _K;
		A.assign(N, INT_MAX);
		B.assign(N, INT_MIN);
		C.assign(N, INT_MAX);
		D.assign(N, INT_MIN);
		for (int i = 0; i < K; i++) {
			A[i] = i;
			B[i] = i;
			C[i] = i / S; 
			D[i] = i / S;
		}
		G.resize(N);
		H.resize(N);
		dbg("_4\n", A, B, C, D);
	}

	bool add_teleporter_fast(int s, int t) {
		if (s < K && t < K)
			return t <= s;
		G[s].push_back(t);
		H[t].push_back(s);

		int p = -1;

		auto dfsc = y_combinator([&](auto dfsc, int u, int k) -> bool {
			if (C[u] <= k)
				return false;
			C[u] = k;
			if (C[u] < D[u] || A[u] <= B[u])
				return true;
			else if (C[u] == D[u])
				p = u;
			for (int v : H[u])
				if (dfsc(v, k))
					return true;
			return false;
		});

		auto dfsd = y_combinator([&](auto dfsd, int u, int k) -> bool {
			if (k <= D[u])
				return false;
			D[u] = k;
			if (C[u] < D[u] || A[u] <= B[u])
				return true;
			else if (C[u] == D[u])
				p = u;
			for (int v : G[u])
				if (dfsd(v, k))
					return true;
			return false;
		});

		if (dfsc(s, C[t]) || dfsd(t, D[s]))
			return true;
		dbg("_4\n", s, t, A, B, C, D);
		if (p == -1)
			return false;
		int b = C[p];

		auto dfsa = y_combinator([&](auto dfsa, int u, int k) -> bool {
			if (A[u] <= k)
				return false;
			A[u] = k;
			if (A[u] <= B[u])
				return true;
			for (int v : H[u])
				if (C[v] == D[v] && C[v] == b && dfsa(v, k))
					return true;
			return false;
		});

		auto dfsb = y_combinator([&](auto dfsb, int u, int k) -> bool {
			if (k <= B[u])
				return false;
			B[u] = k;
			if (A[u] <= B[u])
				return true;
			for (int v : G[u])
				if (C[v] == D[v] && C[v] == b && dfsb(v, k))
					return true;
			return false;
		});

		for (int i = b * S; i < min((b + 1) * S, K); i++) {
			for (int v : H[i])
				if (C[v] == D[v] && C[v] == b && dfsa(v, A[i]))
					return true;
			for (int v : G[i])
				if (C[v] == D[v] && C[v] == b && dfsb(v, B[i]));
					return true;
		}
		dbg(A, B, C, D);
		return false;
	}
}

void init(int N, int K) { game::init_fast(N, K); }

int add_teleporter(int u, int v) { return game::add_teleporter_fast(u, v); }

/*
namespace {

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  // namespace

int main() {
  int N = read_int();
  int M = read_int();
  int K = read_int();
  std::vector<int> u(M), v(M);
  for (int i = 0; i < M; ++i) {
    u[i] = read_int();
    v[i] = read_int();
  }

  init(N, K);
  int i;
  for (i = 0; i < M; ++i) {
    int answer = add_teleporter(u[i], v[i]);
    if (answer != 0 && answer != 1) {
      i = -1;
      break;
    } else if (answer == 1) {
      break;
    }
  }
  printf("%d\n", i);
  return 0;
}
*/

#undef NDEBUG