# include "icc.h"
# include <bits/stdc++.h>
using namespace std;
const int MAXN = 101;
int Root[MAXN];
int Size[MAXN];
set<int> Leaders;
vector<int> Vertexes[MAXN];
int Find(int U)
{
if(Root[U] == U) return U;
return Root[U] = Find(Root[U]);
}
void Merge(int U, int V)
{
U = Find(U);
V = Find(V);
if(U == V) return;
if(Size[U] > Size[V]) swap(U, V);
Size[U] += Size[V];
Root[V] = Root[U];
for(auto& Vertex : Vertexes[V]) Vertexes[U].push_back(Vertex);
Vertexes[V].clear();
Leaders.erase(V);
}
void Conquer(vector<int> A, vector<int> B)
{
if(A.empty() || B.empty()) return;
int SizeA = (int)A.size();
int SizeB = (int)B.size();
int QueryA[MAXN] = {};
int QueryB[MAXN] = {};
for(int i = 0; i < SizeA; i++) QueryA[i] = A[i];
for(int i = 0; i < SizeB; i++) QueryB[i] = B[i];
if(SizeA == 1 && SizeB == 1)
{
setRoad(A[0], B[0]);
Merge(A[0], B[0]);
return;
}
if(SizeB > 1)
{
int SizeC = SizeB / 2;
vector<int> C;
for(int i = 0; i < SizeC; i++)
{
QueryB[i] = B[i];
C.push_back(B[i]);
}
if(query(SizeA, SizeC, QueryA, QueryB) == 0)
{
C.clear();
for(int i = SizeC; i < SizeB; i++)
{
C.push_back(B[i]);
}
}
Conquer(A, C);
}
else
{
int SizeC = SizeA / 2;
vector<int> C;
for(int i = 0; i < SizeC; i++)
{
QueryA[i] = A[i];
C.push_back(A[i]);
}
if(query(SizeC, SizeB, QueryA, QueryB) == 0)
{
C.clear();
for(int i = SizeC; i < SizeA; i++)
{
C.push_back(A[i]);
}
}
Conquer(C, B);
}
}
void Divide(vector<int> A, vector<int> B, bool Lamp)
{
if(A.empty() || B.empty()) return;
int SizeA = 0;
int SizeB = 0;
int QueryA[MAXN] = {};
int QueryB[MAXN] = {};
for(int i = 0; i < (int)A.size(); i++)
{
for(auto& U : Vertexes[A[i]])
{
QueryA[SizeA] = U;
SizeA++;
}
}
for(int i = 0; i < (int)B.size(); i++)
{
for(auto& U : Vertexes[B[i]])
{
QueryB[SizeB] = U;
SizeB++;
}
}
if(Lamp || query(SizeA, SizeB, QueryA, QueryB) == 1)
{
if((int)A.size() == 1 && (int)B.size() == 1)
{
Conquer(Vertexes[A[0]], Vertexes[B[0]]);
return;
}
if((int)B.size() > 1)
{
int SizeC = 0, QSizeC = (int)B.size() / 2;
vector<int> C;
for(int i = 0; i < QSizeC; i++)
{
C.push_back(B[i]);
for(auto& U : Vertexes[B[i]])
{
QueryB[SizeC] = U;
SizeC++;
}
}
if(query(SizeA, SizeC, QueryA, QueryB) == 0)
{
C.clear();
for(int i = QSizeC; i < (int)B.size(); i++)
{
C.push_back(B[i]);
}
}
Divide(A, C, true);
}
else
{
int SizeC = 0, QSizeC = (int)A.size() / 2;
vector<int> C;
for(int i = 0; i < QSizeC; i++)
{
C.push_back(A[i]);
for(auto& U : Vertexes[A[i]])
{
QueryA[SizeC] = U;
SizeC++;
}
}
if(query(SizeC, SizeB, QueryA, QueryB) == 0)
{
C.clear();
for(int i = QSizeC; i < (int)A.size(); i++)
{
C.push_back(A[i]);
}
}
Divide(C, B, true);
}
}
else
{
int SizeC = 0, SizeD = 0;
vector<int> C, D;
for(int i = 0; i < (int)A.size(); i++)
{
if(i < (int)A.size() / 2)
{
C.push_back(A[i]);
for(auto& U : Vertexes[A[i]])
{
QueryA[SizeC] = U;
SizeC++;
}
}
else
{
D.push_back(A[i]);
for(auto& U : Vertexes[A[i]])
{
QueryB[SizeD] = U;
SizeD++;
}
}
}
if(query(SizeC, SizeD, QueryA, QueryB) == 0)
{
C.clear();
D.clear();
int SizeC = (int)B.size() / 2;
for(int i = 0; i < (int)B.size(); i++)
{
if(i < SizeC)
{
C.push_back(B[i]);
}
else
{
D.push_back(B[i]);
}
}
}
Divide(C, D, true);
}
return;
}
void run(int N)
{
for(int U = 1; U <= N; U++)
{
Root[U] = U;
Size[U] = 1;
Vertexes[U].push_back(U);
Leaders.insert(U);
}
int Edges = N - 1;
while(Edges--)
{
int SizeA = (int)Leaders.size() / 2;
int Index = 0;
vector<int> A, B;
for(auto& U : Leaders)
{
if(Index < SizeA)
{
A.push_back(U);
}
else
{
B.push_back(U);
}
Index++;
}
Divide(A, B, false);
}
}
