#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> adj[30001];
vector<int> readj[30001];
int mini[30001];
int maxi[30001];
int K,N;
void init(int32_t n, int32_t k) {
N=n;K=k;
for(int i=0;i<k-1;i++) { adj[i].emplace_back(i + 1); readj[i+1].emplace_back(i);}
for(int i=0;i<k;i++)mini[i]=i;
for(int i=0;i<k;i++)maxi[i]=i;
for(int i=k;i<n;i++)mini[i]=k;
for(int i=k;i<n;i++)maxi[i]=-1;
}
bool ans;
void dfs(int x,int val){
if(maxi[x]>=val or x<K)return;
maxi[x] = val;
if(maxi[x]>=mini[x])ans=true;
for(int&i:adj[x])dfs(i,val);
}
void redfs(int x,int val){
if(mini[x]<=val or x<K)return;
mini[x] = val;
if(maxi[x]>=mini[x])ans=true;
for(int&i:readj[x])redfs(i,val);
}
int32_t add_teleporter(int32_t u, int32_t v) {
if(u==v)return u<K;
if(u<K and v<K){
return v<=u;
}
adj[u].emplace_back(v);
readj[v].emplace_back(u);
dfs(v,maxi[u]);
redfs(u,mini[v]);
return ans;
}
//namespace {
//
// int32_t read_int() {
// int32_t x;
// if (scanf("%d", &x) != 1) {
// fprintf(stderr, "Error while reading input\n");
// exit(1);
// }
// return x;
// }
//
//} // namespace
//
//int32_t main() {
// int32_t N = read_int();
// int32_t M = read_int();
// int32_t K = read_int();
// std::vector<int32_t> u(M), v(M);
// for (int32_t i = 0; i < M; ++i) {
// u[i] = read_int();
// v[i] = read_int();
// }
//
// init(N, K);
// int32_t i;
// for (i = 0; i < M; ++i) {
// int32_t 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;
//}
