#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "icc.h"
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T> using ordset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const int MAXN = 110;
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))
struct union_find {
int par[MAXN];
void init() {
for (int i = 0; i < MAXN; i++) {
par[i] = i;
}
}
int find (int x) {
return x == par[x] ? x : par[x] = find(par[x]);
}
void merge (int x, int y) {
par[find(x)] = find(y);
}
} uf;
int N;
vector<int> verts[MAXN];
int tmpa[MAXN], tmpb[MAXN];
int query (vector<int> a, vector<int> b) {
copy(all(a), tmpa);
copy(all(b), tmpb);
return query(a.size(), b.size(), tmpa, tmpb);
}
vector<int> getverts (vector<int> vc) {
vector<int> v;
for (int c : vc) {
v.insert(v.end(), all(verts[c]));
}
return v;
}
int queryc (vector<int> ca, vector<int> cb) {
return query(getverts(ca), getverts(cb));
}
pii findedge() {
#warning reset!
vector<int> reps;
for (int i = 1; i <= N; i++) {
verts[i].clear();
}
for (int i = 1; i <= N; i++) {
verts[uf.find(i)].push_back(i);
if (i == uf.find(i)) {
reps.push_back(i);
}
}
//ok while it is true
while (true) {
random_shuffle(all(reps));
int f = reps.size() / 2;
vector<int> vca, vcb;
for (int i = 0; i < f; i++) {
int c = reps[i];
vca.push_back(c);
}
for (int i = f; i < reps.size(); i++) {
int c = reps[i];
vcb.push_back(c);
}
if (queryc(vca, vcb)) {
//then great you have it
vector<int> va = getverts(vca), vb = getverts(vcb);
while (va.size() > 1) {
int half = va.size() / 2;
if (query(vector<int> (va.begin(), va.begin() + half), vb)) {
va.resize(half);
} else {
va.erase(va.begin(), va.begin() + half);
}
}
while (vb.size() > 1) {
int half = vb.size() / 2;
if (query(va, vector<int> (vb.begin(), vb.begin() + half))) {
vb.resize(half);
} else {
vb.erase(vb.begin(), vb.begin() + half);
}
}
//ok now we have the components
//get down to vertices
return pii(va[0], vb[0]);
}
}
}
void run (int nnnnn) {
N = nnnnn;
uf.init();
//just randomize it lol
for (int i = 0; i < N - 1; i++) {
pii p = findedge();
setRoad(p.fi, p.se);
uf.merge(p.fi, p.se);
}
}
