#include using namespace std; using pii=pair; using tii=tuple; using qii=tuple; using ll=long long; using ull=unsigned long long; using ld=long double; constexpr int INF=1e9; constexpr ll INF_ll=1e18; #define rep(i,n) for (int i=0;i<(int)(n);i++) #define replr(i,l,r) for (int i=(int)(l);i<(int)(r);i++) #define all(v) v.begin(),v.end() #define len(v) ((int)v.size()) template inline bool chmin(T &a,T b){ if(a>b){ a=b; return true; } return false; } template inline bool chmax(T &a,T b){ if(a inline bool chmin_ref(T &a,const T &b){ if(a>b){ a=b; return true; } return false; } template inline bool chmax_ref(T &a,const T &b){ if(a(now-start).count(); return ms; } int get_ms_all_program(){ auto now=chrono::steady_clock::now(); int ms=chrono::duration_cast(now-program_start).count(); return ms; } } mt19937 mt; uint32_t rand_int(uint32_t r){ //[0,r) assert(r!=0); return ((uint64_t)mt()*r)>>32; } int rand_int(int l,int r){ //[l,r) assert(l T get_random_element(const vector &v){ assert(!v.empty()); return v[rand_int(len(v))]; } template void add(vector &a,vector b){ for(auto i:b) a.push_back(i); } template SA_State SA(const SA_State &first_state,int limit_ms,double start_temp,double end_temp=0.0){ SA_State state=first_state,best_state=state; int loop_cnt=0,accept_cnt=0,update_cnt=0; int ms=0; double temp=start_temp; Timer::snap(); while(true){ if((loop_cnt&63)==63){ ms=Timer::get_ms(); if(limit_ms<=ms) break; //double t=(double)ms/limit_ms; temp=start_temp-(start_temp-end_temp)/limit_ms*ms; //temp=pow(start_temp,1-t)*pow(end_temp,t); } loop_cnt++; double accept_diff=log(rand_double())*temp; bool accepted=state.modify(accept_diff); if(accepted){ accept_cnt++; if(state.score A,B; constexpr ll X=50,L=5e17; namespace Solver{ struct State{ vector actions; ll score=0; State():actions(X){ rep(i,X){ actions[i].first=0; actions[i].second=i%(N-1)+1; } score=calc_score(); } ll calc_score(){ array a=A,b=B; for(auto [u,v]:actions){ a[u]=a[v]=(a[u]+a[v])/2; b[u]=b[v]=(b[u]+b[v])/2; } return max(abs(L-a[0]),abs(L-b[0])); } bool modify1(double accept_diff){ int t=rand_int(X); auto pre_action=actions[t]; actions[t].second=rand_int(1,N); ll new_score=calc_score(); if(accept_diff<=score-new_score){ score=new_score; return true; }else{ actions[t]=pre_action; return false; } } bool modify2(double accept_diff){ int a=rand_int(X),b=rand_int(X); swap(actions[a],actions[b]); ll new_score=calc_score(); if(accept_diff<=score-new_score){ score=new_score; return true; }else{ swap(actions[a],actions[b]); return false; } } bool modify(double accept_diff){ if(rand_int(2)) return modify1(accept_diff); else return modify2(accept_diff); } }; void solve(){ State state; state=SA(state,900,1e15); cout << len(state.actions) << '\n'; for(auto [u,v]:state.actions){ cout << u+1 << ' ' << v+1 << '\n'; } cerr << (int)floor(2000000-100000*log10(state.score+1)) << '\n'; } } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); Timer::program_start_snap(); int n; cin >> n; assert(n==N); rep(i,N) cin >> A[i] >> B[i]; Solver::solve(); exit(0); }