#include<bits/stdc++.h>
#include"Alice.h"
using namespace std;
typedef long long ll;
const int N = 5005;
int x[N][N];
struct dsu {
    vector<int> fa;
    dsu(int n) : fa(n + 2) { iota(fa.begin(), fa.end(), 0); };
    inline int Find(int r) {
        while (r != fa[r]) r = fa[r] = fa[fa[r]];
        return r;
    }
    inline bool Merge(int x, int y) {
        x = Find(x); y = Find(y);
        if (x == y) return true;
        else return fa[y] = x, false;
    }
};
vector<pair<int, int>> Alice() {
    srand(114515);
    ll X = setN(5000);
    for (int i = 2; i <= 5000; i++) 
        for (int j = 1; j < i; j++) 
            x[i][j] = rand() % 60;
    vector<pair<int, int>> E;
    dsu A(5005);
    for (int tot = 0; tot < 5000 - 1;) {
        int u = rand() % 5000 + 1, v = rand() % 5000 + 1;
        if (u == v) continue;
        if (u < v) swap(u, v);
        if (!((X >> x[u][v]) & 1)) continue;
        if (!A.Merge(u, v)) E.push_back({v, u}), tot++;
    }
    sort(E.begin(), E.end());
    return E;
}
// signed main() {
//     freopen("a.out", "w", stdout);
//     auto T = Alice();
//     random_shuffle(T.begin(), T.end());
//     for (int i = 2497; i < 4999; i++) 
//         cout << T[i].first << " " << T[i].second << endl;
// }

#include<bits/stdc++.h>
#include"Bob.h"
using namespace std;
typedef long long ll;
const int N = 5005;
int x[N][N];
// inline int read() {
//     int w = 0, f = 1;
//     char ch = getchar();
//     while (ch < '0' || ch > '9') {
//         if (ch == '-') f = -1;
//         ch = getchar();
//     }
//     while (ch >= '0' && ch <= '9') {
//         w = (w << 1) + (w << 3) + ch - 48;
//         ch = getchar();
//     }
//     return w * f;
// }
long long Bob(vector<pair<int, int>> V) {
    srand(114515);
    ll ans = 0;
    for (int i = 2; i <= 5000; i++) 
        for (int j = 1; j < i; j++) 
            x[i][j] = rand() % 60;
    for (auto [u, v] : V) ans |= (1ll << x[v][u]);
    return ans;
}
// signed main() {
//     freopen("a.out", "r", stdin);
//     vector<pair<int, int>> E;
//     for (int i = 0; i < 2500; i++) {
//         int u = read(), v = read();
//         E.push_back({u, v});
//     }
//     auto X = Bob(E);
//     cout << X << endl;
// }