#include <bits/stdc++.h>
using namespace std;
const int maxn = 1503;
const int k = 40;
int cnt[maxn][maxn];
vector <int> adj[maxn];
int n, cnt_buckets;
void initialize(int m)
{
n = m;
cnt_buckets = (n - 1) / k;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
{
if ((i - 1) / k == (j - 1) / k)
adj[i].push_back(j), adj[j].push_back(i);
else
cnt[(i - 1) / k][(j - 1) / k]++, cnt[(j - 1) / k][(i - 1) / k]++;
}
}
int cnt_used = 0;
bool used[maxn];
void dfs1(int ver)
{
used[ver] = true;
cnt_used++;
for (int i = 0; i <= cnt_buckets; i++)
if (!used[i] && cnt[ver][i])
dfs1(i);
}
void dfs2(int ver)
{
used[ver] = true;
cnt_used++;
for (auto i: adj[ver])
if (!used[i])
dfs2(i);
}
int hasEdge(int u, int v)
{
u++;
v++;
if ((u - 1) / k == (v - 1) / k)
{
auto it1 = find(adj[u].begin(), adj[u].end(), v);
auto it2 = find(adj[v].begin(), adj[v].end(), u);
adj[u].erase(it1);
adj[v].erase(it2);
int first = (u - 1) / k * k + 1;
int last = min(n, first + k - 1);
for (int i = first; i <= last; i++)
used[i] = false;
cnt_used = 0;
dfs2(first);
if (cnt_used != last - first + 1)
{
adj[u].push_back(v);
adj[v].push_back(u);
return 1;
}
return 0;
}
else
{
cnt[(u - 1) / k][(v - 1) / k]--;
cnt[(v - 1) / k][(u - 1) / k]--;
if (cnt[(u - 1) / k][(v - 1) / k] >= 1)
return 0;
for (int i = 0; i <= cnt_buckets; i++)
used[i] = false;
cnt_used = 0;
dfs1(0);
if (cnt_used != cnt_buckets + 1)
{
cnt[(u - 1) / k][(v - 1) / k]++;
cnt[(v - 1) / k][(u - 1) / k]++;
return 1;
}
return 0;
}
}
