/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
typedef long long ll;
const int N_MAX = 102;
const int BITS = 7;
int query (int sa, int sb, int a[], int b[]);
void setRoad (int a, int b);
vector <int> edges[N_MAX];
vector <int> component[N_MAX];
int cntComponents;
bool visited[N_MAX];
void dfs (int u)
{
visited[u] = true;
component[cntComponents].push_back(u);
for(int v : edges[u])
if(visited[v] == false)
dfs(v);
}
int a[N_MAX], b[N_MAX];
int ca[N_MAX], cb[N_MAX];
void run (int n)
{
for(int t = 1; t < n; t++)
{
int U, V;
for(int i = 1; i <= n; i++)
visited[i] = false;
for(int i = 1; i <= n; i++)
if(visited[i] == false)
{
cntComponents++;
dfs(i);
}
int cntca, cntcb;
for(int bit = 0; bit < BITS; bit++)
{
int cnta = 0, cntb = 0;
for(int i = 1; i <= cntComponents; i++)
if((i >> bit) & 1)
{
for(int u : component[i])
a[cnta++] = u;
}
else
{
for(int u : component[i])
b[cntb++] = u;
}
if(query(cnta, cntb, a, b) == true)
{
cntca = 0;
cntcb = 0;
for(int i = 1; i <= cntComponents; i++)
if((i >> bit) & 1)
ca[++cntca] = i;
else
cb[++cntcb] = i;
break;
}
}
int c1, c2;
int l, r;
l = 1;
r = cntca;
while(l < r)
{
int mid = ((l + r) >> 1);
int cnta = 0, cntb = 0;
for(int i = l; i <= mid; i++)
for(int u : component[ca[i]])
a[cnta++] = u;
for(int i = 1; i <= cntcb; i++)
for(int u : component[cb[i]])
b[cntb++] = u;
if(query(cnta, cntb, a, b) == true)
r = mid;
else
l = mid + 1;
}
c1 = ca[l];
l = 1;
r = cntcb;
while(l < r)
{
int mid = ((l + r) >> 1);
int cnta = 0, cntb = 0;
for(int i = 1; i <= cntca; i++)
for(int u : component[ca[i]])
a[cnta++] = u;
for(int i = l; i <= mid; i++)
for(int u : component[cb[i]])
b[cntb++] = u;
if(query(cnta, cntb, a, b) == true)
r = mid;
else
l = mid + 1;
}
c2 = cb[l];
l = 0;
r = (int)component[c1].size() - 1;
while(l < r)
{
int mid = ((l + r) >> 1);
int cnta = 0, cntb = 0;
for(int i = l; i <= mid; i++)
a[cnta++] = component[c1][i];
for(int u : component[c2])
b[cntb++] = u;
if(query(cnta, cntb, a, b) == true)
r = mid;
else
l = mid + 1;
}
U = component[c1][l];
l = 0;
r = (int)component[c2].size() - 1;
while(l < r)
{
int mid = ((l + r) >> 1);
int cnta = 0, cntb = 0;
for(int u : component[c1])
a[cnta++] = u;
for(int i = l; i <= mid; i++)
b[cntb++] = component[c2][i];
if(query(cnta, cntb, a, b) == true)
r = mid;
else
l = mid + 1;
}
V = component[c2][r];
setRoad(U, V);
edges[U].push_back(V);
edges[V].push_back(U);
for(int i = 1; i <= cntComponents; i++)
component[i].clear();
cntComponents = 0;
}
}
