#pragma GCC optimize("Ofast,unroll-loops")
#include "game.h"
#ifndef EVAL
#include "game_grader.cpp"
#endif
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;
namespace
{
const int P = 12;
int n, k, from[300000][7], to[300000][7], where[300000][7];
vector<int> Ef[300000][7], Et[300000][7];
void update_from(int u, int layer, vector<int> &same)
{
if (from[u][layer] == to[u][layer])
same.emplace_back(u);
for (auto v : Ef[u][layer])
if (from[u][layer] > from[v][layer])
{
from[v][layer] = from[u][layer];
update_from(v, layer, same);
}
}
void update_to(int u, int layer, vector<int> &same)
{
if (from[u][layer] == to[u][layer])
same.emplace_back(u);
for (auto v : Et[u][layer])
if (to[u][layer] < to[v][layer])
{
to[v][layer] = to[u][layer];
update_to(v, layer, same);
}
}
void build(int i = 1, int L = 0, int R = k - 1, int l = 0)
{
for (int j = L; j <= R; j++)
where[j][l] = i;
if (L != R)
{
int range = (R - L + P) / P;
for (int j = 1; j <= P; j++)
{
int ml = L + range * (j - 1), mr = min(R, L + range * j - 1);
for (int p = ml; p <= mr; p++)
from[p][l] = to[p][l] = j;
if (ml <= mr)
build(i * P + (j - 1), ml, mr, l + 1);
}
}
else
from[L][l] = 2, to[L][l] = 1;
}
int add_edge(int, int, int, int);
int add_node(int u, int i, int l)
{
if (where[u][l])
return 0;
where[u][l] = i;
from[u][l] = 0, to[u][l] = P + 1;
bool flag = 0;
for (auto v : Et[u][l - 1])
if (where[u][l] == where[v][l])
flag |= add_edge(v, u, i, l);
for (auto v : Ef[u][l - 1])
if (where[u][l] == where[v][l])
flag |= add_edge(u, v, i, l);
return flag | (from[u][l] > to[u][l]);
}
int add_edge(int u, int v, int i = 1, int l = 0)
{
Ef[u][l].emplace_back(v);
Et[v][l].emplace_back(u);
vector<int> s;
bool flag = 0;
if (v >= k && from[v][l] < from[u][l])
{
from[v][l] = from[u][l];
update_from(v, l, s);
flag |= (from[v][l] > to[v][l]);
}
if (u >= k && to[u][l] > to[v][l])
{
to[u][l] = to[v][l];
update_to(u, l, s);
flag |= (from[u][l] > to[u][l]);
}
if (where[u][l + 1] == where[v][l + 1] && where[u][l + 1] > 0)
flag |= add_edge(u, v, where[u][l + 1], l + 1);
for (int w : s)
flag |= add_node(w, i * P + (from[w][l] - 1), l + 1);
return flag;
}
}
void init(int n, int k)
{
::n = n, ::k = k;
build();
for (int i = k; i < n; i++)
{
from[i][0] = 0, to[i][0] = P + 1;
where[i][0] = 1;
}
}
int add_teleporter(int u, int v)
{
if (u < k && v < k)
{
if (v <= u)
return 1;
return 0;
}
bool ans = add_edge(u, v);
// cout << u << ' ' << v << '\n';
// for (int p = 0; p < 5; p++)
// for (int i = 0; i < n; i++)
// cout << from[i][p] << ' ' << to[i][p] << ' ' << " \n"[i == n - 1];
// for (int p = 0; p < 5; p++)
// for (int i = 0; i < n; i++)
// cout << where[i][p] << " \n"[i == n - 1];
// cout << '\n';
return ans;
}
