/* Author : Mychecksdead */
#include "park.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;
static int Place[1400];
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rng(34236234);
int rn(int l, int r){
return uniform_int_distribution<int>(l,r)(rng);
}
int n;
bool ask(int a, int b, vi u){
for(int i = 0; i < n; ++i) Place[i] = 0;
if(a > b) swap(a, b);
Place[a] = 1;
Place[b] = 1;
for(int x: u) Place[x] = 1;
return Ask(a, b, Place);
}
bool ask2(int a, int b, vi u){
for(int i = 0; i < n; ++i) Place[i] = 1;
for(int x: u) Place[x] = 0;
if(a > b) swap(a, b);
return Ask(a, b, Place);
}
void answer(int a, int b){
if(a>b) swap(a, b);
// cerr << a << ' ' << b << '\n';
Answer(a, b);
}
vi chain_solver(vector<int> nodes){
if(nodes.size() <= 1) return nodes;
// cerr << "chain solve: ";
// for(int x: nodes) cerr << x << ' ';
// cerr << '\n';
int v = nodes[rn(0, int(nodes.size())-1)];
vector<vi> C;
vector<int> U;
for(int u: nodes){
if(u != v){
bool is = ask(u, v, vi{});
if(is){
answer(u, v);
C.pb(vi{u});
U.pb(u);
}
}
}
for(int u: nodes){
bool is = 0;
for(int x: U) is = is | (x == u);
if(u != v && !is){
int l = 0, r = int(U.size()) - 2, res = int(U.size()) - 1;
while(l <= r){
int mid = l+r>>1;
vi to_pop;
for(int i = 0; i <= mid; ++i) to_pop.pb(U[i]);
if(ask2(v, u, to_pop) == 0){
res = mid;
r = mid - 1;
}else{
l = mid + 1;
}
}
C[res].pb(u);
}
}
vector<vi> res;
for(auto &V: C){
res.pb(chain_solver(V));
}
if(res.size() == 1){
if(res[0].back() != U[0]) reverse(all(res[0]));
res[0].pb(v);
return res[0];
}
if(res[0].back() != U[0]) reverse(all(res[0]));
if(res[1][0] != U[1]) reverse(all(res[1]));
res[0].pb(v);
for(int x: res[1]) res[0].pb(x);
return res[0];
}
void solve(vector<int> nodes){
if(nodes.size() <= 1) return;
// cerr << "solve: ";
// for(int x: nodes) cerr << x << ' ';
// cerr << '\n';
if(nodes.size() == 2){
answer(nodes[0], nodes[1]);
return;
}
// int v = nodes[0];//nodes[rn(0, int(nodes.size())-1)];
int A = nodes[rn(0, int(nodes.size()) - 1)];
int B = nodes[rn(0, int(nodes.size()) - 1)];
while(B == A){
B = nodes[rn(0, int(nodes.size()) - 1)];
}
// cerr << A << ' ' << B << '\n';
vi cur = nodes;
vector<vi> C;
vector<int> U;
while(cur.size()){
int v = cur.back();
cur.pop_back();
if(v == A || v == B) continue;
if(ask2(A, B, vi{v}) == 0){
// its in
C.pb({});
U.pb(v);
}
}
U = chain_solver(U);
if(U.size()){
if(ask(A, U[0], vi{}) == 0) reverse(all(U)), reverse(all(C));
answer(A, U[0]);
answer(B, U.back());
}else{
answer(A, B);
}
C.insert(C.begin(), vi{});
U.insert(U.begin(), A);
C.pb({});
U.pb(B);
// cerr << "U :";
// for(int x: U) cerr << x << ' ';
// cerr << '\n';
// cerr << A << ' ' << B << '\n';
for(int u: nodes){
bool is = false;
for(int x: U) is = is | (x == u);
if(is) continue;
int l = 0, r = int(U.size()) - 2, res = int(U.size()) - 1;
while(l <= r){
int mid = l+r>>1;
vi to_pop = {U[mid]};
if(ask2(B, u, to_pop)){
l = mid + 1;
}else{
res = mid;
r = mid - 1;
}
}
// cerr << res << ' ' << u << '\n';
C[res].pb(u);
}
for(int i = 0; i < int(U.size()); ++i){
// for(int u: C[i]){
// if(ask(u, U[i], vi{})){
// answer(u, U[i]);
// break;
// }
// }
C[i].pb(U[i]);
}
for(auto V: C){
solve(V);
}
}
void Detect(int t, int nn) {
n = nn;
if(t == 1){
for(int i = 0; i < n; ++i){
for(int j = i + 1; j < n; ++j){
if(ask(i, j, vi{})){
answer(i, j);
}
}
}
}else{
vi v;
for(int i = 1; i <= n; ++i){
v.pb(i-1);
}
solve(v);
}
}
