#include<bits/stdc++.h>
#include "meetings.h"
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int>Merge_sort(vector<int>now,int mn){
if (now.size()==1) return now;
int n=now.size(),mid=(n-1)/2;
vector<int>l,r,ans;
for (int i=0;i<=mid;i++)
l.push_back(now[i]);
for (int i=mid+1;i<n;i++)
r.push_back(now[i]);
l=Merge_sort(l,mn);
r=Merge_sort(r,mn);
int p=0;
for (auto i:l){
if (p>=r.size()){
ans.push_back(i);
continue;
}
int small=Query(mn,i,r[p]);
while(p<r.size()&&small==r[p]){
ans.push_back(r[p++]);
if (p<r.size())
small=Query(mn,i,r[p]);
}
ans.push_back(i);
}
while (p<r.size())
ans.push_back(r[p++]);
return ans;
}
set<pii>ans;
void DC(vector<int>have,int dep){
// cout<<dep<<" "<<have.size()<<'\n';
int n=have.size();
if (n==1) return;
else if (n==2){
// cout<<"n=2 add : "<<min(have[0],have[1])<<" "<<max(have[0],have[1])<<'\n';
assert(have[0]!=have[1]);
ans.insert({min(have[0],have[1]),max(have[0],have[1])});
return;
}
shuffle(have.begin(),have.end(),rng);
int p1=have[0],p2=have[1];
vector<vector<int> >all(n);
vector<int>path;
map<int,int>mp;
/*
cout<<"solve : ";
for (auto i:have)
cout<<i<<" ";
cout<<'\n';
cout<<"root is "<<p1<<" "<<p2<<'\n';
*/
path.push_back(p2);
all[0].push_back(p1);
all[1].push_back(p2);
for (int id=2;id<n;id++){
int i=have[id];
int nxt=Query(p1,i,p2);
if (nxt==i)
path.push_back(i);
if (nxt!=p1&&nxt!=p2){
if (!mp[nxt]) mp[nxt]=id;
all[mp[nxt]].push_back(i);
}
else if (nxt==p1)
all[0].push_back(i);
else all[1].push_back(i);
}
/*
for (int i=0;i<n;i++){
if (!all[i].empty()){
cout<<"son "<<i<<" : ";
for (auto j:all[i])
cout<<j<<" ";
cout<<'\n';
}
}
cout<<"path : "<<p1<<' ';
for (auto i:path)
cout<<i<<" ";
cout<<'\n';
*/
path=Merge_sort(path,p1);
// cout<<"add "<<min(p1,path[0])<<' '<<max(p1,path[0])<<'\n';
assert(p1!=path[0]);
ans.insert({min(p1,path[0]),max(p1,path[0])});
for (int i=1;i<path.size();i++){
// cout<<"add "<<min(path[i],path[i-1])<<" "<<max(path[i],path[i-1])<<'\n';
assert(path[i]!=path[i-1]);
ans.insert({min(path[i],path[i-1]),max(path[i],path[i-1])});
}
for (int i=0;i<n;i++){
if (!all[i].empty()){
DC(all[i],dep+1);
}
}
}
void Solve(int N){
vector<int>dq;
for (int i=0;i<N;i++)
dq.push_back(i);
DC(dq,0);
for (auto i:ans){
// assert(i.x!=i.y);
// assert(i.x<i.y);
// cout<<i.x<<" "<<i.y<<'\n';
Bridge(i.x,i.y);
}
}
