#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;i>n; vector>a(n); cin>>a; dsu uf(n); vectoredge; vector>to(n); vectorcnt(n,0); vectorseen(n,false); rep(i,n-1)reps(j,i+1,n){ int x=a[i].first-a[j].first,y=a[i].second-a[j].second; edge.push_back({i,j,x*x+y*y}); } //sort(all(edge),comp); // sort(all(edge),[&](pair g,pair h)->bool { // int sx=a.at(g.first).first-a.at(g.second).first,sy=a.at(g.first).second-a.at(g.second).second; // int gx=a.at(h.first).first-a.at(h.second).first,gy=a.at(h.first).second-a.at(h.second).second; // // int sx=a[g.first].first-a[g.second].first,sy=a[g.first].second-a[g.second].second; // // int gx=a[h.first].first-a[h.second].first,gy=a[h.first].second-a[h.second].second; // return sx*sx+sy*syque; 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]){ seen[x]=true; seen[i]=true; ans.push_back({i+1,x+1}); } } } } cout<