#include "park.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define tern(cond, a, b) (cond ? a : b)
typedef long long lint;
typedef pair<lint,lint> ii;
vector<int> done;
static int place[1400];
static int indone[1400];
int n;
int query(int S, int E, vector<int> stuff, bool assumedone=true){
if(S > E) swap(S,E);
for(int i = 0;i < n;i++) place[i] = 0;
for(int x : stuff) place[x] = 1;
if(assumedone) for(int x : done) place[x] = 1;
place[S] = 1, place[E] = 1;
//show2(S,E);
//for(int i = 0;i < n;i++) cerr << place[i]; cerr << endl;
return Ask(S, E, place);
}
void findmiddle(int S, int E, vector<int> &v){
vector<int> possible;
for(int i = 0;i < n;i++){
if(i == S or i == E or indone[i]) continue;
possible.push_back(i);
}
random_shuffle(all(possible));
//for(int x : possible) cerr << x << " "; cerr << endl;
if(query(S, E, {})){
v.push_back(E);
return;
}
int low = 0, high = sz(possible)-1;
while(low < high){
int mid = (low+high)/2;
vector<int> toask;
for(int i = 0;i < sz(possible);i++){
if(low <= i and i <= mid) continue;
toask.push_back(possible[i]);
}
if(query(S, E, toask)) low = mid+1;
else high = mid;
//for(int x : toask) cerr << x << " "; cerr << endl;
}
//show3(S, E, possible[low]);
findmiddle(S, possible[low], v);
findmiddle(possible[low],E,v);
}
void answer(int A, int B){
if(A > B) swap(A,B);
show2(A,B);
Answer(A,B);
}
void Detect(int T, int _n){
n = _n;
if(T == 1){
for(int i = 0;i < n;i++){
for(int j = i+1;j < n;j++){
if(query(i,j,{i,j},false)){
answer(i,j);
}
}
}
return;
}
int seed = time(0);
srand(seed);
show(seed);
vector<int> possible;
for(int i = 1;i < n;i++) possible.push_back(i);
done.push_back(0);
indone[0] = 1;
while(true){
vector<int> undone;
for(int i = 0;i < n;i++) if(not indone[i]) undone.push_back(i);
if(sz(undone) == 0) break;
vector<int> erm;
findmiddle(0, undone[rand()%sz(undone)], erm);
//for(int x : erm) cerr << x << " "; cerr << endl;
int low = -1, high = sz(done)-1;
int u = erm[0];
while(low != high-1){
int mid = (low+high)/2;
vector<int> stuff;
for(int i = 0;i <= mid;i++) stuff.push_back(done[i]);
if(query(0, u, stuff, false)) high = mid;
else low = mid;
}
//show2(u, done[high]);
answer(u, done[high]);
for(int i = 1;i < sz(erm);i++) answer(erm[i-1], erm[i]);
///push back into order
for(int x : erm){
done.push_back(x);
indone[x] = 1;
}
}
}
