#include <bits/stdc++.h>
#include "meetings.h"

//#define int long long
#define ll long long
#define ld long double
//#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;
int inf=1000000007;
ll infl=1000000000000000007;
ll mod=1000000007;
ll mod1=998244353;

const int N=2007;

set<int>G[N];
bool odw[N];
bool was[N];
int s[N];

void del(int u,int v)
{
	G[v].erase(u);
	G[u].erase(v);
	//cout<<"DEL "<<u<<" "<<v<<endl;
}
void add(int u,int v)
{
	G[v].insert(u);
	G[u].insert(v);
	//cout<<"ADD "<<u<<" "<<v<<endl;
}

void dfs(int v,int o)
{
	s[v]=1;
	for(auto u:G[v]) 
	{
		if(u==o||odw[v]) continue;
		dfs(u,v);
		s[v]+=s[u];
	}
}

void Solve(int n)
{
	vector<int>V;
	for(int i=0;i<n;i++) V.pb(i);
	random_shuffle(all(V));
	add(V[0],V[1]);
	for(int i=2;i<n;i++)
	{
		if(was[V[i]]) continue;
		memset(odw,0,sizeof odw);
		int r=V[0];
		//cout<<"XD "<<V[i]<<endl;
		while(true)
		{
			dfs(r,0);
			int v=r;
			while(true)
			{
				int nx=-1;
				for(auto u:G[v]) if(!odw[u]&&s[u]>i/2&&s[u]<s[v]) nx=u;
				if(nx==-1) break;
				v=nx;
			}
			odw[v]=1;
			//cout<<v<<endl;
			vector<pair<int,int>>X;
			for(auto u:G[v]) if(!odw[u]) X.pb({s[u],u});
			sort(all(X),greater<pair<int,int>>());
			bool is=0,is1=0;
			for(auto [k,u]:X)
			{
				int t=Query(v,u,V[i]);
				if(t!=v)
				{
					if(t==u) 
					{
						r=u;
						is1=1;
					}
					else if(t==V[i])
					{
						is=1;
						del(u,v);
						add(u,V[i]);
						add(V[i],v);
					}
					else
					{
						is=1;
						del(u,v);
						add(u,t);
						add(t,v);
						add(t,V[i]);
					}
					break;
				}
			}
			if(is) break;
			if(!is1)
			{
				add(v,V[i]);
				break;
			}
		}
	}
	for(int u=0;u<n;u++) for(auto v:G[u]) if(u<v) Bridge(u,v);
}