#include "park.h"
#include <vector>
#include <map>
#include <iostream>
using namespace std;
static int Place[1400];
int Deg[1400]={};
int query(int u,int v)
{
Place[u]=Place[v]=1;
if (u>v)
swap(u,v);
int z=Ask(u,v,Place);
Place[u]=Place[v]=0;
return z;
}
map<int,int>vis;
int n;
map<pair<int,int>,bool>done,ed;
int sg(int u,int v)
{
if (u>v)
swap(u,v);
if (ed.find({u,v})==ed.end())
ed[{u,v}]=query(u,v);
return ed[{u,v}];
}
void rec(int u,int v)
{
if (vis[v])
return;
if (sg(u,v))
{
vis[v]=1;
if (u>v)
swap(u,v);
if (done[{u,v}]) return;
done[{u,v}]=1;
Deg[u]++;
Deg[v]++;
Answer(u,v);return;
}
vector<int>nodes;
for (int i=0;i<n;i++)
{
if (i==u||i==v||Deg[i]==7) continue;
nodes.push_back(i);
}
if (nodes.size()==0)
{
Answer(min(u,v),max(u,v));return;
}
int st=-1,en=nodes.size()-1;
while (st+1<en)
{
int mid=(st+en)/2;
for (int i=0;i<=mid;i++)
Place[nodes[i]]=1;
if (query(u,v))
en=mid;
else
st=mid;
for (int i=0;i<=mid;i++)
Place[nodes[i]]=0;
}
rec(u,nodes[en]);rec(nodes[en],v);
}
void Detect(int T, int N)
{
n=N;
if (N==2)
{
Answer(0,1);return;
}
for (int i=0;i<N;i++)
Deg[i]=0;
for (int i=1;i<N;i++)
rec(0,i);
}
