#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace atcoder; using namespace std; using ll=long long; using ull=unsigned long long; using P=pair; templateusing minque=priority_queue,greater>; templatebool chmax(T &a,const T &b){return (abool chmin(T &a,const T &b){return (a>b?(a=b,true):false);} templateostream &operator<<(ostream &os,const pair&p){os<istream &operator>>(istream &is,pair&p){is>>p.first>>p.second;return is;} template ostream &operator<<(ostream &os,const vector &a){cout<<'{';for(int i=0;iistream &operator>>(istream &is,vector &a){for(auto &i:a)is>>i;return is;} #define reps(i,a,n) for(int i=(a);i<(n);i++) #define rep(i,n) reps(i,0,n) #define all(x) x.begin(),x.end() #define pcnt(x) __builtin_popcount(x) ll myceil(ll a,ll b){return (a+b-1)/b;} template void debug(const T1& x,const T2& ...y){ #ifdef LOCAL cout<>testcase; for(int i=0;ia,pairb){ int dx=a.first-b.first,dy=a.second-b.second; return dx*dx+dy*dy; } bool comp(E a,E b){return a.dst>n; vector>a(n); rep(i,n){ int x,y; cin>>x>>y; a[i]={x,y}; } dsu uf(n); vectoredge; vector>to(n); vectorcnt(n,0); vectorseen(n,false); rep(i,n){ vectorcu; rep(j,n)if(i!=j){ cu.push_back({i,j,abs(a[i],a[j])}); } sort(all(cu),comp); edge.insert(edge.end(),cu.begin(),cu.begin()+min(20,cu.size())); } sort(all(edge),comp); for(auto [u,v,dst]:edge){ if(uf.same(u,v))continue; uf.merge(u,v); to[u].push_back(v); to[v].push_back(u); cnt[u]++,cnt[v]++; } queueque; rep(i,n)if(cnt[i]==1)que.push(i); vector>ans; while(!que.empty()){ int x=que.front(); que.pop(); for(auto i:to[x]){ if(!seen[i]){ cnt[i]--; que.push(i); if(!seen[x]){ ans.push_back({i+1,x+1}); seen[i]=seen[x]=true; } } } } cout<