#include using ll = long long; using std::pair; using std::vector; namespace inner { std::random_device seed_gen; std::mt19937_64 engine(0); template T randint(T l, T r) { assert(l <= r); return std::uniform_int_distribution(l, r)(engine); } template T randint(T x) { assert(0 < x); return std::uniform_int_distribution(0, x - 1)(engine); } template T randreal(T l, T r) { assert(l <= r); return std::uniform_real_distribution(l, r)(engine); } template T randnorm(T mean, T stddev) { assert(stddev > 0); return std::normal_distribution(mean, stddev)(engine); } template size_t randdist(const vector& dist) { assert(dist.size() > 0); vector acc(dist.size() + 1); for (size_t i = 0; i < dist.size(); i++) { assert(dist[i] >= 0); acc[i + 1] = acc[i] + dist[i]; } assert(acc.back() > 0); return std::upper_bound(acc.begin(), acc.end(), randreal(0, acc.back())) - acc.begin() - 1; } template void shuffle(vector& v) { std::shuffle(v.begin(), v.end(), engine); } template T randchoice(const vector& v) { return v[randint(v.size())]; } auto start_time = std::chrono::system_clock::now(); /** * @brief ms */ uint64_t elapsed_time() { return (std::chrono::system_clock::now() - inner::start_time).count() / 1000000; } } // namespace inner struct Solver { static const ll ANS_MAX; const ll N; vector A; vector B; Solver(const ll& _N, const vector& _A, const vector& _B) : N(_N), A(_A), B(_B) { } pair calc(const vector>& c) { assert(c.size() <= 50); vector tmp_A(A); vector tmp_B(B); for (auto [u, v] : c) { assert(0 <= u and u < N); assert(0 <= v and v < N); tmp_A.at(u) = tmp_A.at(v) = (tmp_A.at(u) + tmp_A.at(v)) / 2; tmp_B.at(u) = tmp_B.at(v) = (tmp_B.at(u) + tmp_B.at(v)) / 2; } return {std::abs(tmp_A[0] - 500'000'000'000'000'000), std::abs(tmp_B[0] - 500'000'000'000'000'000)}; } ll max(const pair& p) { return std::max(p.first, p.second); } vector> solve() { vector> best_ans(N - 1); for (ll i = 0; i < N - 1; i++) { best_ans[i] = {0, i + 1}; } ll best_score = max(calc(best_ans)); while (inner::elapsed_time() <= 180) { vector> ans(ANS_MAX); for (ll i = 0; i < ANS_MAX; i++) { ll u, v; do { u = inner::randint(N); v = inner::randint(N); } while (u == v or (i == ANS_MAX - 1 and u != 0 and v != 0)); ans[i] = {u, v}; } ll score = max(calc(ans)); if (score < best_score) { best_score = score; best_ans = ans; } } while (inner::elapsed_time() <= 980) { vector> ans(best_ans); ll idx = inner::randint(N); auto [u, v] = [&]() -> pair { ll u, v; do { u = inner::randint(N); v = inner::randint(N); } while (u == v or (idx == ANS_MAX - 1 and u != 0 and v != 0)); return {u, v}; }(); ans[idx] = {u, v}; ll score = max(calc(ans)); if (score < best_score) { best_score = score; best_ans = ans; } } std::cerr << "a = " << best_score << std::endl; return best_ans; } }; const ll Solver::ANS_MAX = 50; int main() { ll N; std::cin >> N; vector A(N), B(N); for (int i = 0; i < N; i++) std::cin >> A[i] >> B[i]; Solver solver(N, A, B); vector> ans = solver.solve(); std::cout << ans.size() << std::endl; for (auto [u, v] : ans) { std::cout << u + 1 << " " << v + 1 << std::endl; } }