// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl
#define umap unordered_map
#define uset unordered_set
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
const int INF = 1'000'000'007;
#include "game.h"
vi graph[300005];
int max_reach[300005];
int N,K;
bool stop=0;
void dfs(int u) {
//cout<<"u = "<<u<<" max_reach = "<<max_reach[u]<<endl;
if(max_reach[u]>=u) {
stop=1;
return;
}
trav(v,graph[u]) if(max_reach[u]>max_reach[v]) {
max_reach[v]=max_reach[u];
dfs(v);
}
}
void init(int n, int k) {
N=n;
K=k;
memset(max_reach,-1,sizeof(max_reach));
}
int add_teleporter(int u, int v) {
//cout<<"u = "<<u<<" v = "<<v<<endl;
graph[u].pb(v);
if(u<K) max_reach[v]=max(max_reach[v],u);
max_reach[v]=max(max_reach[v],max_reach[u]);
dfs(v);
//cout<<endl;
return stop;
}
/*
#include <cstdio>
#include <cstdlib>
#include <vector>
#include "game.h"
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;
}
*/
