#include <bits/stdc++.h>
#include "icc.h"
#define ll long long
#define fi first
#define se second
using namespace std;
const int maxn = 110;
int lena, lenb;
vector <int> comp[maxn];
int par[maxn];
int a[maxn];
int b[maxn];
int bio[maxn];
vector <int> head;
vector <int> va;
vector <int> vb;
//bool query(int f, int g, int h[], int j[]){
// for(int i = 0; i < lena; i++) cout << a[i] << ' ';
// cout << ": ";
// for(int i = 0; i < lenb; i++) cout << b[i] << ' ';
// cout << endl;
// bool odg;
// cin >> odg;
// return odg;
//}
//void setRoad(int x, int y){
// cout << "cesta: " << x << ' ' << y << endl;
//}
void run(int n){
srand(time(0));
for(int i = 1; i <= n; i++){
comp[i].push_back(i);
par[i] = i;
}
for(int k = n; k >= 2; k--){
head.clear();
for(int i = 1; i <= n; i++){
if(par[i] == i) head.push_back(i);
}
while(true){
memset(bio, -1, sizeof bio);
int cnt = 0;
while(cnt < k / 2){
int x = head[rand() % k];
if(bio[x] != -1) continue;
// cout << x << endl;
bio[x] = 1;
cnt++;
}
lena = 0;
lenb = 0;
for(int i = 0; i < k; i++){
if(bio[head[i]] == 1){
for(auto x: comp[head[i]]){
b[lenb] = x;
lenb++;
}
}
else {
for(auto x: comp[head[i]]){
a[lena] = x;
lena++;
}
}
}
if(query(lena, lenb, a, b) == 1) break;
}
va.clear();
vb.clear();
// for(int i = 0; i < lena; i++){
// for(auto x: comp[a[i]]) va.push_back(x);
// }
//
// for(int i = 0; i < lenb; i++){
// for(auto x: comp[b[i]]) vb.push_back(x);
// }
//
// for(int i = 0; i < va.size(); i++){
// a[i] = va[i];
// }
//
// for(int i = 0; i < vb.size(); i++){
// b[i] = vb[i];
// }
//
// lena = va.size();
// lenb = vb.size();
for(int i = 0; i < lena; i++) va.push_back(a[i]);
for(int i = 0; i < lenb; i++) vb.push_back(b[i]);
int lo = 0, hi = lena - 1;
while(lo < hi){
int mid = (lo + hi) / 2;
lena = 0;
for(int i = 0; i <= mid; i++){
a[lena] = va[i];
lena++;
}
if(query(lena, lenb, a, b) == 1) hi = mid;
else lo = mid + 1;
}
int x = a[hi];
lena = 1;
a[0] = x;
lo = 0, hi = lenb - 1;
while(lo < hi){
int mid = (lo + hi) / 2;
lenb = 0;
for(int i = 0; i <= mid; i++){
b[lenb] = vb[i];
lenb++;
}
if(query(lena, lenb, a, b) == 1) hi = mid;
else lo = mid + 1;
}
int y = b[hi];
setRoad(x, y);
for(auto i: comp[par[y]]){
par[i] = par[x];
comp[par[x]].push_back(i);
}
}
}
//int main(){
// int n;
// cin >> n;
//
// run(n);
//
// return 0;
//}
