//#pragma once
//#include "grader.cpp"
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
int n,mat[305][305],br,leaf[305],used[305],used2[305],lamp;
map<int,int>m[305];
void prec()
{
for(int i=1;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
mat[i][j]=Query(0,i,j);
}
}
}
void fix()
{
for(int i=1;i<n;i++)
{
if(leaf[i]==2)
{
Bridge(0,i);
}
}
lamp=1;
}
void resh()
{
int num_leaf=0;
for(int i=1;i<n;i++)
{
if(leaf[i])continue;
for(int j=i+1;j<n;j++)
{
if(leaf[j])continue;
used[mat[i][j]]++;
}
}
for(int i=1;i<n;i++)
{
if(leaf[i])continue;
if(!used[i])
{
num_leaf++;
leaf[i]=2;
}
}
if(num_leaf+1==br)
{
fix();
return;
}
for(int i=1;i<n;i++)
{
if(leaf[i]==2)
{
for(int j=i+1;j<n;j++)
{
if(leaf[j]==2)
{
used2[mat[i][j]]++;
m[mat[i][j]][i]=1;
}
}
}
}
int sz;
for(int i=1;i<n;i++)
{
if(leaf[i]==1)continue;
//cout<<used[i]<<" "<<used2[i]<<" "<<m[i].size()<<endl;
sz=m[i].size();
if(used[i]==used2[i]+m[i].size()+1)
{
//cout<<i<<endl;
for(auto j=m[i].begin();j!=m[i].end();j++)
{
Bridge(min(i,j->first),max(i,j->first));
leaf[j->first]=1;
br--;
}
for(int j=1;j<n;j++)
{
if(leaf[j]==1||j==i)continue;
if(mat[min(i,j)][max(i,j)]==i)
{
//cout<<i<<" "<<j<<endl;
Bridge(min(i,j),max(i,j));
leaf[j]=1;
br--;
}
}
}
}
for(int i=1;i<n;i++)
{
m[i].clear();
if(leaf[i]==2)leaf[i]=0;
}
memset(used,0,sizeof(used));
memset(used2,0,sizeof(used2));
}
void Solve(int N)
{
n=N;
br=n;
prec();
int b=0;
//cout<<endl;
while(!lamp)
{
resh();
//b++;
//cout<<br<<endl;
//if(b==1)return;
}
}
