#include "park.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
int is_in[1401];
vi graph[1401];
int n;
vi cur_tree;
vi rest;
vi ls;
bool odw[1401];
void dfs(int v)
{
odw[v] = 1;
ls.pb(v);
forall(it,graph[v])
{
if(!odw[it]) dfs(it);
}
}
void calc_ls(int a, vi not_use = {})
{
rep(i,n) odw[i] = 0;
forall(it,not_use) odw[it] = 1;
ls = {};
dfs(a);
}
bool query(int a, int b, vi x)
{
rep(i,n) is_in[i] = 0;
is_in[a] = 1;
is_in[b] = 1;
if(a > b) swap(a,b);
forall(it,x) is_in[it] = 1;
return Ask(a,b,is_in);
}
void make_path(int a, int b)
{
if(a == b) return;
int l = -1;
int r = siz(rest)-1;
int r2 = -2;
while(l <= r)
{
int mid = (l+r)/2;
vi q;
rep2(i,0,mid) q.pb(rest[i]);
if(!query(a,b,q))
{
r2 = mid;
l = mid+1;
}
else
{
r = mid-1;
}
}
r2++;
int new_a;
if(r2 == -1) new_a = b;
else new_a = rest[r2];
if(new_a == b)
{
graph[a].pb(b);
graph[b].pb(a);
}
if(new_a != b)
{
cur_tree.pb(new_a);
swap(rest[r2],rest[siz(rest)-1]);
rest.pop_back();
make_path(new_a,b);
make_path(a,new_a);
}
}
int rep_[1401];
int fint(int v)
{
if(v == rep_[v]) return v;
return rep_[v] = fint(rep_[v]);
}
void onion(int a, int b)
{
rep_[fint(a)] = fint(b);
}
void comp_rek(int v, int a)
{
calc_ls(a,graph[v]);
if(!query(v,a,ls)) return;
int l = 0;
int r = siz(ls)-2;
int ans = siz(ls)-1;
while(l <= r)
{
int mid = (l+r)/2;
vi q;
rep(i,mid+1) q.pb(ls[i]);
if(query(v,a,q))
{
ans = mid;
r = mid-1;
}
else
{
l = mid+1;
}
}
a = ls[ans];
graph[v].pb(a);
graph[a].pb(v);
rep(i,n)
{
rep_[i] = i;
is_in[i] = 0;
}
forall(it,graph[v]) is_in[it] = 1;
is_in[v] = 1;
rep(i,n) forall(it,graph[i]) if(!is_in[i] && !is_in[it]) onion(i,it);
set<int> dif;
forall(it,graph[a]) if(!is_in[it]) dif.insert(fint(it));
forall(it,dif) comp_rek(v,it);
}
void Detect(int T, int N)
{
random_start();
mt.seed(2137);
n = N;
rep(i,n) graph[i] = {};
cur_tree = {0};
rest = {};
rep2(i,1,n-1) rest.pb(i);
shuffle(all(rest),mt);
while(siz(cur_tree) != n)
{
int ind_b = los(0,siz(rest)-1);
int b = rest[ind_b];
calc_ls(0);
int l = 0;
int r = siz(ls)-1;
int root = -1;
while(l <= r)
{
int mid = (l+r)/2;
vi q;
rep(i,mid+1) q.pb(ls[i]);
forall(it,rest) q.pb(it);
if(!query(0,b,q))
{
root = mid;
l = mid+1;
}
else
{
r = mid-1;
}
}
root++;
vi tree_;
swap(rest[ind_b],rest[siz(rest)-1]);
rest.pop_back();
rep(i,root+1) tree_.pb(ls[i]);
make_path(ls[root],b);
cur_tree.pb(b);
}
rep(v,n)
{
rep(i,n)
{
rep_[i] = i;
is_in[i] = 0;
}
forall(it,graph[v]) is_in[it] = 1;
is_in[v] = 1;
rep(i,n) forall(it,graph[i]) if(!is_in[i] && !is_in[it]) onion(i,it);
set<int> dif;
forall(it,graph[v])
{
forall(it2,graph[it])
{
if(!is_in[it2]) dif.insert(fint(it2));
}
}
forall(it,dif) comp_rek(v,it);
}
rep(i,n) forall(it,graph[i]) if(it > i) Answer(i,it);
}
