#define _USE_MATH_DEFINES #pragma GCC target("avx2") #pragma GCC optimize("O3") #include #include #include #include #include #include using namespace std; #define LP(I,S,G) for (long long int I = (S); I < (G); ++I) #define IN(X) for (int in = 0; in < X.size(); in++)cin >> X[in] #define OUT(X) for (int in = 0; in < X.size(); in++)cout << X[in]<<" " #define SORT(X) sort((X).begin(), (X).end()) #define CSORT(X,Y) sort(X.begin(), X.end(),Y) #define COPY(X,Y) copy(X.begin(), X.end(), Y.begin()) #define ALL(X,Y) for (auto (X) :(Y)) #define FULL(a) (a).begin(),(a).end() #define BFS(Q,S) for(Q.push(S);Q.size()!=0;Q.pop()) typedef long long int ll; typedef unsigned long long int ull; long long int M = 998244353; chrono::system_clock::time_point starttime; using namespace std::chrono; #ifndef ONLINE_JUDGE #define DEBUG #endif inline float getTime() { #ifdef DEBUG return duration_cast(system_clock::now() - starttime).count() /4.0; #else return duration_cast(system_clock::now() - starttime).count(); #endif } int dx[] = { -1,0,1,0 }, dy[] = { 0,1,0,-1 }; ll MAX(ll A, ll B) { return ((A) > (B) ? (A) : (B)); } ll MIN(ll A, ll B) { return ((A) < (B) ? (A) : (B)); } inline long long int xor128() { static long long int x = 123456789, y = 362436069, z = 521288629, w = 88675123; long long int t = (x ^ (x << 11)); x = y; y = z; z = w; return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8))); } long long int pow_n(long long int x, long long int n) { if (n == 0) return 1; if (n % 2 == 0) return pow_n(x * x, n / 2); else return x * pow_n(x, n - 1); } ll border = 5 * pow_n(10, 17); double calc_score(vector a, vector b, vector>& ans) { for (int i = 0; i < ans.size(); ++i) { int u = ans[i].first, v = ans[i].second; a[u] = a[v] = (a[u] + a[v]) / 2; b[u] = b[v] = (b[u] + b[v]) / 2; } return log10(abs(border - a[0])+ abs(border - b[0]) + 1); } int main(int argc, char* argv[]) { starttime = chrono::system_clock::now(); ios::sync_with_stdio(false); std::cin.tie(nullptr); mt19937 rnd(0); ll n, t = 50, now = 0; cin >> n; vector a(n), b(n); LP(i, 0, n)cin >> a[i] >> b[i]; vector> ans(t); LP(i, 0, t) { ans[i].first = xor128() % n; ans[i].second = xor128() % (n - 1); if (ans[i].second >= ans[i].first)++ans[i].second; } double score = calc_score(a, b, ans); vector table(t); for (int i = 0; i < t; ++i)table[i] = i; double time; shuffle(table.begin(), table.end(), rnd); int cnt = 0; while ((time=getTime()) <= 950) { double temp = 0.75*(950 - time) / 950.0; int i = table[now]; int bx = ans[i].first, by = ans[i].second; ans[i].first = xor128() % n; ans[i].second = xor128() % (n - 1); if (ans[i].first != 0 && ans[i].second != 0 && xor128() % 10 == 0)ans[i].first = 0; if (ans[i].second >= ans[i].first)++ans[i].second; double new_score = calc_score(a, b, ans); if (xor128() % 10000 < exp((score-new_score) / temp) * 10000) { score = new_score; } else { ans[i].first = bx; ans[i].second = by; } ++cnt; if (++now == t) { now = 0; shuffle(table.begin(), table.end(), rnd); } } cerr << cnt; for (int i = 0; i < ans.size(); ++i) { int u = ans[i].first, v = ans[i].second; a[u] = a[v] = (a[u] + a[v]) / 2; b[u] = b[v] = (b[u] + b[v]) / 2; } cerr << "score:" << ll(2000000 - 100000 * log10(max(abs(border - a[0]), abs(border - b[0])) + 1)) << "\n"; cerr << a[0] << " " << b[0] << "\n"; cout << ans.size() << "\n"; ALL(x, ans)cout << x.first+1 << " " << x.second+1 << "\n"; exit(0); }