#include "park.h"
#include<bits/stdc++.h>
using namespace std;
int N, ap[1500], cc[1500];
vector < int > v[1500];
void addEdge (int S, int T)
{
v[S].push_back (T);
v[T].push_back (S);
}
void findPath (int S, int T, vector < int > possible)
{
if (S > T)
swap (S, T);
int place[N];
for (int i=0; i<N; i++)
place[i] = 0;
place[S] = place[T] = 1;
if (Ask (S, T, place))
{
addEdge (S, T);
return ;
}
int p = 0, u = possible.size () - 1, mij, ras = -1;
while (p <= u)
{
mij = (p + u) >> 1;
for (int i=0; i<=mij; i++)
place[possible[i]] = 1;
bool queryResult = Ask (S, T, place);
for (int i=0; i<=mij; i++)
place[possible[i]] = 0;
if (queryResult) ras = possible[mij], u = mij - 1;
else p = mij + 1;
}
///ras is definitely on the path from S to T
while (possible.back () != ras)
possible.pop_back ();
possible.pop_back ();
findPath (S, ras, possible);
findPath (ras, T, possible);
}
void Detect (int subtaskId, int nn)
{
N = nn;
int place[N];
if (subtaskId == 1)
{
memset (place, 0, sizeof (place));
for (int i=0; i<N; i++)
for (int j=i + 1; j<N; j++)
{
place[i] = place[j] = 1;
if (Ask (i, j, place))
Answer (i, j);
place[i] = place[j] = 0;
}
return ;
}
for (int i=1; i<N; i++)
if (v[i].empty ())
{
memset (ap, 0, sizeof (ap));
int bfsLength = 1;
cc[1] = 0, ap[0] = 1;
for (int j=1; j<=bfsLength; j++)
for (auto it : v[cc[j]])
if (ap[it] == 0)
ap[it] = 1, cc[++bfsLength] = it;
int p = 1, u = bfsLength, mij, ras = 0;
while (p <= u)
{
mij = (p + u) >> 1;
for (int j=0; j<N; j++)
if (ap[j] == 0) place[j] = 1;
else place[j] = 0;
for (int j=1; j<=mij; j++)
place[cc[j]] = 1;
if (Ask (cc[1], i, place)) ras = mij, u = mij - 1;
else p = mij + 1;
}
vector < int > others;
for (int j=0; j<N; j++)
if (ap[j] == 0 && j != i)
others.push_back (j);
int node = cc[ras];///this one is the closest to i
findPath (node, i, others);
}
for (int i=0; i<N; i++)
for (auto j : v[i])
if (i < j)
Answer (i, j);
}
