#include "game.h"
//apio 2022 game

//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>
#include <bitset>

#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 n, k;
bitset<MX> reach[MX];
bitset<MX> qq;

//hi is the largest node that can reach u
//lo is the smallest node u can reach
//if hi[u] >= lo[u] there is a cycle

void init(int _n, int _k){
	n = _n, k = _k;
	for(int i = k-2; i>=0; i--){
		reach[i][i+1] = 1;
		reach[i] |= reach[i+1];
	}
}

int add_teleporter(int a, int b){
	if(a == b && a < k) return 1;
	if(a < k && b < k && b < a) return 1;
	reach[a][b] = 1;
	reach[a] |= reach[b];
	for(int i = 0; i<n; i++){
		if(reach[i][a]){
			reach[i] |= reach[b];
			reach[i][b] = 1;
		}
	}
	qq.reset();
	for(int i = 0; i<k; i++){
		qq[i] = 1;
		if((qq&reach[i]).count()) return 1;
	}
	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;
}

**/