#include "park.h"
#include <algorithm>
#include <cstring>
int lst[2005], to[3005], pre[3005], vis[2005], seq[2005], tot, n, cnt;
bool can_go[2005], rem[2005], in[2005];
inline bool query(int u, int v)
{
if (u > v)
std::swap(u, v);
static int qry[2005];
for (int i = 0; i < n; i++)
qry[i] = can_go[i];
return Ask(u, v, qry);
}
inline void add_edge(int u, int v)
{
if (u > v)
std::swap(u, v);
Answer(u, v);
auto add_e = [&] (int x, int y)
{
to[tot] = y;
pre[tot] = lst[x];
lst[x] = tot++;
};
add_e(u, v);
add_e(v, u);
}
inline int get_min(int u)
{
int l = 0, r = n - 1, res = -1;
while (l <= r)
{
int m = l + r >> 1;
for (int i = 0; i <= m; i++)
can_go[i] = vis[i] != 2;
for (int i = m + 1; i < n; i++)
can_go[i] = vis[i] == 1;
can_go[u] = true;
if (query(0, u))
{
res = m;
r = m - 1;
}
else
l = m + 1;
}
return res;
}
void clear(int u)
{
rem[u] = false;
for (int i = lst[u]; ~i; i = pre[i])
{
if (rem[to[i]])
clear(to[i]);
}
}
void dfs(int u)
{
seq[cnt++] = u;
in[u] = true;
for (int i = lst[u]; ~i; i = pre[i])
{
if (rem[to[i]] && !in[to[i]])
dfs(to[i]);
}
}
inline void get_edge(int u)
{
for (int i = 0; i < n; i++)
rem[i] = vis[i] == 1;
int rt = 0;
while (rt < n)
{
if (!rem[rt])
{
rt++;
continue;
}
memcpy(can_go, rem, n);
can_go[u] = true;
if (!query(u, rt))
{
clear(rt++);
continue;
}
cnt = 0;
memset(in, false, n);
dfs(rt);
int l = 0, r = cnt - 1, res = -1;
while (l <= r)
{
int m = l + r >> 1;
for (int i = 0; i < cnt; i++)
can_go[seq[i]] = i <= m;
if (query(rt, u))
{
res = m;
r = m - 1;
}
else
l = m + 1;
}
add_edge(u, seq[res]);
rem[seq[res]] = false;
}
}
inline bool connect(int u)
{
for (int i = 0; i < n; i++)
can_go[i] = vis[i] == 1;
can_go[u] = true;
return query(0, u);
}
void add_node(int u)
{
vis[u] = 2;
while (!connect(u))
add_node(get_min(u));
get_edge(u);
vis[u] = 1;
}
void Detect(int, int N)
{
n = N;
memset(lst, -1, n << 2);
vis[0] = 1;
for (int i = 0; i < n; i++)
{
if (!vis[i])
add_node(i);
}
}
