#include "icc.h"
#include <bits/stdc++.h>
#define ll long long
#define el cout << endl
#define ii pair<int, int>
#define fi first
#define se second
#define BIT(n) ((1ll) << (n))
#define bit(mask, i) (((mask) >> (i)) & (1))
using namespace std;
const int maxn = 1e2;
struct DSU
{
int n;
vector<int> leader, sz, ele[maxn + 10];
DSU(int n = 0) : n(n)
{
leader.assign(n + 10, 0);
sz.assign(n + 10, 1);
iota(leader.begin(), leader.end(), 0);
for (int i = 1; i <= n; i++)
ele[i].push_back(i);
}
int find_leader(int x)
{
if (x == leader[x])
return x;
return leader[x] = find_leader(leader[x]);
}
void connect(int x, int y)
{
x = find_leader(x);
y = find_leader(y);
if (x == y)
return ;
if (sz[x] < sz[y])
swap(x, y);
sz[x] += sz[y];
leader[y] = x;
for (int a : ele[y])
ele[x].push_back(a);
}
};
int do_query(vector<int> a, vector<int> b)
{
int sz_a = a.size();
int sz_b = b.size();
int _a[sz_a];
int _b[sz_b];
for (int i = 0; i < sz_a; i++)
_a[i] = a[i];
for (int i = 0; i < sz_b; i++)
_b[i] = b[i];
return query(sz_a, sz_b, _a, _b);
}
namespace SUBTASK_1
{
int n;
DSU D;
void run(int N)
{
n = N;
D = DSU(n);
for (int _ = 1; _ <= n - 1; _++)
{
for (int i = 1; i <= n; i++)
{
bool flag = 0;
for (int j = i + 1; j <= n; j++)
{
if (D.find_leader(i) == D.find_leader(j))
continue;
if (do_query({i}, {j}))
{
setRoad(i, j);
D.connect(i, j);
flag = 1;
break;
}
}
if (flag)
break;
}
}
}
bool check_sub(int n)
{
return n == 15;
}
};
namespace SUBTASK_2
{
int n;
DSU D;
void run(int N)
{
n = N;
D = DSU(n);
for (int _ = 1; _ < n; _++)
{
vector<int> x;
for (int i = 1; i <= n; i++)
{
vector<int> y;
for (int j = 1; j <= n; j++)
{
if (D.find_leader(i) == D.find_leader(j))
continue;
y.push_back(j);
}
if (do_query({i}, y))
x.push_back(i);
}
assert(x.size() == 2);
D.connect(x[0], x[1]);
setRoad(x[0], x[1]);
}
}
};
namespace SUBTASK_3
{
const int maxlog = 6;
int n;
DSU D;
void run(int N)
{
n = N;
D = DSU(n);
for (int _ = 1; _ <= n - 1; _++)
{
for (int j = 0; j <= maxlog; j++)
{
vector<int> x, y;
for (int i = 1; i <= n; i++)
{
// cout << "HELLO: " << i << ' ' << D.find_leader(i), el;
if (bit(D.find_leader(i), j))
x.push_back(i);
else
y.push_back(i);
}
// sort(x.begin(), x.end());
// sort(y.begin(), y.end());
// x.resize(unique(x.begin(), x.end()) - x.begin());
// y.resize(unique(y.begin(), y.end()) - y.begin());
if (do_query(x, y))
{
auto get_pre = [&] (vector<int> &x, int p)
{
vector<int> ans;
for (int i = 0; i <= p; i++)
ans.push_back(x[i]);
return ans;
};
auto check_set = [&] (int p_1, int p_2)
{
return do_query(get_pre(x, p_1), get_pre(y, p_2));
};
auto find_a = [&] (int l, int r)
{
while (l < r)
{
int m = l + r >> 1;
if (check_set(m, y.size() - 1))
r = m;
else
l = m + 1;
}
return r;
};
int A = x[find_a(0, x.size() - 1)];
auto find_b = [&] (int l, int r)
{
while (l < r)
{
int m = l + r >> 1;
if (do_query({A}, get_pre(y, m)))
r = m;
else
l = m + 1;
}
return r;
};
int B = y[find_b(0, y.size() - 1)];
D.connect(A, B);
setRoad(A, B);
break;
}
}
}
}
};
namespace SUBTASK_5
{
const int maxlog = 6;
int n;
DSU D;
void run(int N)
{
n = N;
D = DSU(n);
for (int _ = 1; _ <= n - 1; _++)
{
int mask = 0;
int diff = -1;
for (int j = 0; j <= maxlog; j++)
{
vector<int> x, y;
for (int i = 1; i <= n; i++)
{
if (bit(D.find_leader(i), j))
x.push_back(i);
else
y.push_back(i);
}
if (do_query(x, y))
{
diff = j;
mask |= BIT(j);
}
}
vector<int> x, y;
for (int i = 1; i <= n; i++)
{
if (bit(D.find_leader(i), diff))
x.push_back(i);
else
y.push_back(i);
}
auto get_pre = [&] (vector<int> &x, int p)
{
vector<int> ans;
for (int i = 0; i <= p; i++)
ans.push_back(x[i]);
return ans;
};
auto check_set = [&] (int p_1, int p_2)
{
return do_query(get_pre(x, p_1), get_pre(y, p_2));
};
auto find_a = [&] (int l, int r)
{
while (l < r)
{
int m = l + r >> 1;
if (check_set(m, y.size() - 1))
r = m;
else
l = m + 1;
}
return r;
};
int A = x[find_a(0, x.size() - 1)];
vector<int> ny = D.ele[D.find_leader(A) ^ mask];
if (y.size() > ny.size())
swap(y, ny);
auto find_b = [&] (int l, int r)
{
while (l < r)
{
int m = l + r >> 1;
if (do_query({A}, get_pre(y, m)))
r = m;
else
l = m + 1;
}
return r;
};
int B = y[find_b(0, y.size() - 1)];
D.connect(A, B);
setRoad(A, B);
}
}
};
void run(int N)
{
SUBTASK_5::run(N);
}
