#include "park.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1405;
const int M=3050;
static int pl[1400];
int use[N],n;
int query(int u, int v)
{
if(u>v) swap(u,v);
for(int i=0;i<n;i++) pl[i]=use[i];
return Ask(u,v,pl);
}
int fir[N],nxt[M],tot,nod[M];
void Add(int u, int v){ tot++;nxt[tot]=fir[u];fir[u]=tot;nod[tot]=v;}
void AddEdge(int u, int v)
{
if(u>v) swap(u,v);
Answer(u,v);
Add(u,v);
Add(v,u);
}
int col[N];
int all(int x, int y)
{
for(int i=0;i<n;i++) use[i]=col[i]==1;
use[x]=use[y]=1;
return query(x,y);
}
int Get(int x, int y)
{
int top=n-1,bot=0,mid,ans;
while(top>=bot)
{
mid=top+bot>>1;
for(int i=0;i<=mid;i++) use[i]=col[i]!=2;
for(int i=mid+1;i<n;i++) use[i]=col[i]==1;
use[x]=use[y]=1;
if(query(x,y)) ans=mid,top=mid-1;
else bot=mid+1;
}
return ans;
}
int was[N];
void Del(int y)
{
was[y]=0;
for(int i=fir[y];i;i=nxt[i]) if(was[nod[i]]) Del(nod[i]);
}
int in[N];
vector<int> nodes;
void DFS(int y)
{
nodes.push_back(y);in[y]=1;
for(int i=fir[y];i;i=nxt[i]) if(!in[nod[i]] && was[nod[i]]) DFS(nod[i]);
}
void Edge(int x)
{
for(int i=0;i<n;i++) was[i]=col[i]==1;
for(int y=0;y<n;y++)
{
if(!was[y]) continue;
for(int i=0;i<n;i++) use[i]=was[i];
use[x]=use[y]=1;
if(!query(x,y)){ Del(y);continue;}
for(int i=0;i<n;i++) in[i]=0;
nodes.clear();
DFS(y);
int top=(int)nodes.size()-1,bot=0,mid,ans;
while(top>=bot)
{
mid=top+bot>>1;
for(int i=0;i<n;i++) use[i]=0;
for(int i=0;i<=mid;i++) use[nodes[i]]=1;
use[x]=use[y]=1;
if(query(x,y)) ans=nodes[mid],top=mid-1;
else bot=mid+1;
}
AddEdge(x,ans);
was[ans]=0;
y--;
}
}
void Work(int x)
{
col[x]=2;
while(!all(0,x)) Work(Get(0,x));
Edge(x);
col[x]=1;
}
void Detect(int T, int N)
{
n=N;col[0]=1;
for(int i=1;i<n;i++) if(!col[i]) Work(i);
}
