#include "park.h"
#include <cstdio>
#include <vector>
using namespace std;
#define si(x) (int)(x.size())
static int Place[1400], n, fin[1400], chk[1400], U[1400], vi[1400];
static vector<int>E[1400], TP, PP;
void Tra(int a){
vi[a]=1;
TP.push_back(a);
for(auto &t: E[a]){
if(U[t] || vi[t])continue;
Tra(t);
}
}
void Go(int rt, int a, int cer){
for(int i=0;i<n;i++)vi[i]=0;
TP.clear();
Tra(rt);
int m = si(TP);
if(!cer){
for(int i=0;i<n;i++)Place[i]=0;
for(int i=0;i<m;i++)Place[TP[i]]=1;
Place[a] = 1;
if(!Ask(min(rt,a),max(rt,a),Place))return;
}
int b = 1, e = m-1, r = m;
while(b<=e){
int mid = (b+e)>>1;
for(int i=0;i<n;i++)Place[i]=0;
for(int i=0;i<mid;i++)Place[TP[i]]=1;
Place[a]=1;
if(Ask(min(rt,a),max(rt,a),Place)){
r = mid;
e = mid-1;
}
else b = mid+1;
}
int x = TP[r-1];
PP.push_back(x);
U[x] = 1;
for(auto &y : E[x]){
if(!U[y]){
Go(y, a, 0);
}
}
}
void Add(int a){
int i;
PP.clear();
for(i=0;i<n;i++)U[i]=0;
Go(0, a, 1);
fin[a] = 1;
for(auto &t: PP){
Answer(min(a, t),max(a,t));
E[a].push_back(t);
E[t].push_back(a);
}
}
void DFS(int a){
chk[a] = 1;
int c = 0;
for(int i=0;i<n;i++){
if(chk[i]||fin[i])continue;
c++;
}
int b = 0, e = c, mid, r = -1;
while(b<=e){
mid = (b+e)>>1;
for(int i=0;i<n;i++){
Place[i] = fin[i];
}
int t=0;
for(int i=0;i<n;i++){
if(chk[i]||fin[i])continue;
if(t<mid){
Place[i] = 1;
}
t++;
}
Place[a] = 1;
if(Ask(0, a, Place)){
r = mid;
e = mid-1;
}
else b = mid+1;
}
if(r == 0){
Add(a);
return;
}
else{
int t=0, x = -1;
for(int i=0;i<n;i++){
if(chk[i]||fin[i])continue;
t++;
if(t==r)x = i;
}
DFS(x);
DFS(a);
}
}
void Detect(int T, int N) {
n = N;
int i;
fin[0]=1;
for(i=1;i<N;i++){
if(fin[i])continue;
DFS(i);
}
}
