#define NDEBUG #include #include #include #include #include #include #include #include using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(i64 i=0; i<(i64)(n); i++) #define repr(i,n) for(i64 i=(i64)(n)-1; i>=0; i--) const i64 INF = 5001001001001001001; const char* yn(bool x){ return x ? "Yes" : "No"; } template void chmin(A& l, const A& r){ if(r < l) l = r; } template void chmax(A& l, const A& r){ if(l < r) l = r; } template using nega_queue = std::priority_queue,std::greater>; using namespace std; const i64 TARGET_INT = 500'000'000'000'000'000; const int OFFSET_SIZE = 6; #include #include #include namespace nachia{ class Xoshiro256pp{ public: using i32 = int32_t; using u32 = uint32_t; using i64 = int64_t; using u64 = uint64_t; private: uint64_t s[4]; // https://prng.di.unimi.it/xoshiro256plusplus.c static inline uint64_t rotl(const uint64_t x, int k) noexcept { return (x << k) | (x >> (64 - k)); } inline uint64_t gen(void) noexcept { const uint64_t result = rotl(s[0] + s[3], 23) + s[0]; const uint64_t t = s[1] << 17; s[2] ^= s[0]; s[3] ^= s[1]; s[1] ^= s[2]; s[0] ^= s[3]; s[2] ^= t; s[3] = rotl(s[3], 45); return result; } // https://xoshiro.di.unimi.it/splitmix64.c u64 splitmix64(u64& x) { u64 z = (x += 0x9e3779b97f4a7c15); z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9; z = (z ^ (z >> 27)) * 0x94d049bb133111eb; return z ^ (z >> 31); } public: void seed(u64 x = 7001){ assert(x != 0); s[0] = x; for(int i=1; i<4; i++) s[i] = splitmix64(x); } Xoshiro256pp(){ seed(); } u64 rng64() { return gen(); } u64 operator()(){ return gen(); } // generate x : l <= x <= r u64 random_unsigned(u64 l,u64 r){ assert(l<=r); r-=l; auto res = rng64(); if(res<=r) return res+l; u64 d = r+1; u64 max_valid = 0xffffffffffffffff/d*d; while(true){ auto res = rng64(); if(res<=max_valid) break; } return res%d+l; } // generate x : l <= x <= r i64 random_signed(i64 l,i64 r){ assert(l<=r); u64 unsigned_l = (u64)l ^ (1ull<<63); u64 unsigned_r = (u64)r ^ (1ull<<63); u64 unsigned_res = random_unsigned(unsigned_l,unsigned_r) ^ (1ull<<63); return (i64)unsigned_res; } // permute x : n_left <= x <= n_right // output r from the front template std::vector random_nPr(Int n_left, Int n_right, Int r){ Int n = n_right-n_left; assert(n>=0); assert(r<=(1ll<<27)); if(r==0) return {}; assert(n>=r-1); std::vector V; std::unordered_map G; for(int i=0; i void permute_inplace(std::vector& V,std::vector perm){ assert(V.size() == perm.size()); int N=V.size(); for(int i=0; i std::vector shuffle(const std::vector& V){ int N=V.size(); auto P = random_nPr(0,N-1,N); std::vector res; res.reserve(N); for(int i=0; i void shuffle_inplace(std::vector& V){ int N=V.size(); permute_inplace(V,random_nPr(0,N-1,N)); } }; } // namespace nachia #include #include nachia::Xoshiro256pp rng; namespace RngInitInstance { struct RngInit { RngInit(){ unsigned long long seed1 = std::random_device()(); unsigned long long seed2 = std::chrono::high_resolution_clock::now().time_since_epoch().count(); rng.seed(seed1 ^ seed2); } } a; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector A(N), B(N); rep(i,N) cin >> A[i] >> B[i]; i64 minWeight = INF; vector minWeightPerm(N); vector> offset; auto WeightFromAB = [](i64 a, i64 b){ i64 ad = abs(a - TARGET_INT); i64 bd = abs(b - TARGET_INT); return max(ad, bd) * 2 + ad + bd; }; auto MakeMove = [&](int a, int b){ A[a] = A[b] = (A[a]+A[b])/2; B[a] = B[b] = (B[a]+B[b])/2; offset.push_back({a,b}); }; while(offset.size() < OFFSET_SIZE){ { int argmin = 1; i64 minw = INF; for(int i=1; i w){ argmin = i; minw = w; } } if(A[argmin] != A[0] || B[argmin] != B[0]){ MakeMove(0, argmin); continue; } } if((int)offset.size()+2 > OFFSET_SIZE) break; { i64 minw = INF; int ma = 1, mb = 2; for(int a=1; a w){ ma = a; mb = b; minw = w; } } MakeMove(ma, mb); MakeMove(0, mb); } } cerr << "A[0] = " << A[0] << endl; cerr << "B[0] = " << B[0] << endl; rep(i,N) minWeightPerm[i] = N-1-i; vector Q = minWeightPerm; vector Qp = minWeightPerm; auto evalQ = [&]() -> i64 { i64 a = A[Q[0]]; i64 b = B[Q[0]]; for(int i=1; i> 32) * i) >> 32; swap(Q[j], Q[i]); } i64 w = evalQ(); rep(ss,20) for(int i=0; i> ans; rep(i,OFFSET_SIZE) ans.push_back(offset[i]); rep(i,N-1) ans.push_back({ Q[i], Q[i+1] }); cout << ans.size() << '\n'; for(auto [u,v] : ans) cout << (u+1) << ' ' << (v+1) << '\n'; return 0; }