#include "game.h"

//misaka will carry me to master
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <cassert>
#include <algorithm>
#include <vector>
#include <functional>
#include <numeric>
#include <set>
#include <map>

#define ll long long
#define lb long double
#define sz(vec) ((int)(vec.size()))
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define kill(x, s) {int COND = x; if(COND){ cout << s << "\n"; return ; }}

const lb eps = 1e-9;
const ll mod = 1e9 + 7, ll_max = 1e18;
//const ll mod = (1 << (23)) * 119 +1, ll_max = 1e18;
const int MX = 3e4 +10, int_max = 0x3f3f3f3f;

struct {
  template<class T>
  operator T() {
    T x; std::cin >> x; return x;
  }
} in;

using namespace std;


int hi[MX], lo[MX];
vector<int> adj[MX], jda[MX];

int n, k;

void init(int _n, int _k){
	 n = _n, k = _k;
	 for(int i = k; i<n; i++){
			hi[i] = -int_max, lo[i] = int_max;
	 }
}

void dfs(int u, int nv){
	//cerr << u << " " << nv << " " << lo[u] << "\n";
	if(hi[u] >= nv) return ;
	hi[u] = nv;
	if(u < k) return ;
	for(int v : adj[u]){
		if(hi[v] < nv) dfs(v, nv);
	}
}

void sfd(int u, int nv){
	//cerr << u << " " << nv << " " << lo[u] << "\n";

	if(lo[u] <= nv) return ;
	lo[u] = nv;
	if(u < k) return ;
	for(int v : jda[u]){
		if(lo[v] > nv) sfd(v, nv);
	}	
}

int add_teleporter(int a, int b){
	int A = (a < k), B = (b < k);
	if(A && B && b == a) return 1;
	if(A && B && b < a) return 1;
	if(A && B) return 0;
	jda[b].pb(a);
	adj[a].pb(b);
	//cerr << A << " "<< B << "\n";
	if(A^B){
		if(A){
			if(lo[b] <= a) return 1;
			dfs(b, a);
		}else{
			if(hi[a] >= b) return 1;
			sfd(a, b);
		}
	}else{
		if(hi[a] >= lo[b]) return 1;
		dfs(b, hi[a]);
		sfd(a, lo[b]);
	}
	return 0;
}


/**
void solve(){
	int n = in, m = in, k = in;
	init(n, k);
	for(int i = 1; i<=m; i++){
		int a = in, b = in;
		if(add_teleporter(a, b)) exit(0);
		cerr << i << "\n";
	}
}

int main(){
  cin.tie(0) -> sync_with_stdio(0);

  int T = 1;
  //cin >> T;
  for(int i = 1; i<=T; i++){
		solve();
	}
  return 0;
}

**/