#include "park.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vpii = vector<pii>;
#define sz(x) int(x.size())
int N;
const int maxN = 1400;
static int Place[maxN];
vi parent(maxN, 0);
vi inserted(maxN, 0);
vi children[maxN];
bool ask(int A, int B, int Place[])
{
return Ask(min(A, B), max(A, B), Place);
}
void answer(int a, int b)
{
Answer(min(a, b), max(a, b));
}
bool connected(int u, int v)
{
// cerr << "connected\n";
for(int i = 0; i < N; i++)
Place[i] = 0;
Place[u] = Place[v] = 1;
return ask(u, v, Place);
}
void dfs(int u, int x, int y, vi& res, vi& vis)
{
vis[u] = 1;
for(int v : children[u])
dfs(v, x, y, res, vis);
if(u != x && u != y)
res.push_back(u);
}
vi ordering(int x, int y)
{
vi vis(N, 0);
vi res;
dfs(0, x, y, res, vis);
for(int i = 0; i < N; i++)
if(!vis[i] && i != x && i != y)
res.push_back(i);
return res;
}
// int xyz = 0;
void insert_node(int u, int a)
{
if(inserted[u]) return;
// cerr << "insert node " << u << ' ' << a << '\n';
// xyz++;
// if(xyz>=10)
// while(1);
if(connected(u, a))
{
parent[u] = a;
children[a].push_back(u);
inserted[u] = 1;
return;
}
vi searchlist = ordering(u, a);
// cerr << u << ' ' << a << " : ";
// for(int x : searchlist)
// cerr << x << ' ';
// cerr << '\n';
while(sz(searchlist) > 1)
{
int md = sz(searchlist)/2;
vi lft, rgt;
for(int i = 0; i < sz(searchlist); i++)
{
if(i < md)
lft.push_back(searchlist[i]);
else
rgt.push_back(searchlist[i]);
}
for(int i = 0; i < N; i++)
Place[i] = 1;
for(int f : lft)
Place[f] = 0;
if(!ask(u, a, Place))
searchlist = lft;
else
searchlist = rgt;
}
// cerr << u << ' ' << a << " : " << "z = " << searchlist[0] << '\n';
int z = searchlist[0];
insert_node(u, z);
insert_node(z, a);
}
void Detect(int T, int N_)
{
N = N_;
inserted[0] = 1;
for(int i = 1; i < N; i++)
insert_node(i, 0);
for(int i = 1; i < N; i++)
answer(i, parent[i]);
}
