/* [Author : Hoang Duy Vu] - THPT Chuyen Nguyen Du */
//#pragma GCC optimize(" unroll-loops")
//#pragma gcc optimize("Ofast")
//#pragma GCC optimization("Ofast")
//#pragma optimize(Ofast)
#include "game.h"
#include <bits/stdc++.h>
#define All(x) (x).begin(),(x).end()
#define ll long long
#define C make_pair
#define fi first
#define se second
#define two second.first
#define thr second.second
#define TASK "txt"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) {
if (res < val) { res = val; return true; } return false; }
template<typename T> bool minimize(T &res, const T &val) {
if (res > val) { res = val; return true; } return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
const int LOG = 20;
const int INF = 1e9 + 7;
const ll LNF = 1e18 + 7;
const int mod = 1e9 + 7;
const int Nx = 3e5 + 100;
int val[2][Nx];
vector <int> a[2][Nx];
int n , k;
int ok;
void init(int _n , int _k)
{
n = _n;
k = _k;
for (int i = 0 ; i < k ; i++)
{
val[0][i] = i;
val[1][i] = i - 1;
}
for (int i = k ; i <= n ; i++)
{
val[0][i] = INF;
val[1][i] = -INF;
}
}
void dfs(int id , int u, int gt)
{
// cout << id << " " << u << " " << gt << " " << val[id][u] << "\n";
int old = val[id][u];
if (id) maximize(val[id][u],gt);
else minimize(val[id][u],gt);
if (val[1][u] >= val[0][u]) {
ok = 1;
return ;
}
if (old == val[id][u]) return ;
for (int v : a[id][u])
dfs(id,v,gt);
}
int add_teleporter(int u, int v)
{
if (u > v && u < k) return 1;
a[1][u].push_back(v);
a[0][v].push_back(u);
ok = 0;
int gt = val[1][u];
if (u < k) gt = u;
dfs(1,v,gt);
gt = val[0][v];
if (v < k) gt = v;
dfs(0,u,gt);
if (ok == 1) return 1;
return 0;
}
// int main()
// {
// if(fopen(TASK".inp", "r")){
// freopen(TASK".inp","r",stdin);
// freopen(TASK".out","w",stdout);
// }
// int x , y , z;
// cin >> x >> y >> z;
// init(x,y);
// for (int i = 1 ; i <= z ; i++)
// {
// int a , b;
// cin >> a >> b;
// if (add_teleporter(a,b))
// {
// (cout << i);
// return 0;
// }
// }
// return 0;
// }
