#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[u]) continue;
		dfs(u,v);
		s[v]+=s[u];
	}
}

void Solve(int n)
{
	srand(time(NULL));
	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];
		int xd=1;
		while(true)
		{
			dfs(r,0);
			int v=r;
			while(true)
			{
				int nx=-1;
				for(auto u:G[v]) if(!odw[u]&&s[u]>s[r]/2&&s[u]<s[v]) nx=u;
				if(nx==-1) break;
				v=nx;
			}
			odw[v]=1;
			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(int j=0;j<sz(X);)
            {
                int u=X[j].st;
                if(j+1==sz(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]);
                            was[t]=1;
                        }
                        break;
                    }
                    j++;
                }
                else
                {
                    int w=X[j].st;
                    int t=Query(u,w,V[i]);
                    if(t!=v)
                    {
                        if(t==u)
                        {
                            r=u;
                            is1=1;
                        }
                        else if(t==w)
                        {
                            r=w;
                            is1=1;
                        }
                        else if(t==V[i])
                        {
                            is=1;
                            if(Query(u,v,V[i])==V[i])
                            {
                                del(u,v);
                                add(u,V[i]);
                                add(V[i],v);
                            }
                            else
                            {
                                del(w,v);
                                add(w,V[i]);
                                add(V[i],v);
                            }
                        }
                        else
                        {
                            is=1;
                            if(Query(u,v,V[i])==t)
                            {
                                del(u,v);
                                add(u,t);
                                add(t,v);
                                add(t,V[i]);
                                was[t]=1;
                            }
                            else
                            {
                                del(w,v);
                                add(w,t);
                                add(t,v);
                                add(t,V[i]);
                                was[t]=1;
                            }
                        }
                        break;
                    }
                    j+=2;
                }
            }
			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);
}