#include "Alice.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace {
struct Edge{
int x, y;
Edge(){}
Edge(int x, int y): x(x), y(y){}
};
const int n = 5000, k = 60;
vector<Edge> vec[k];
void init(){
for(int i=1; i<=n; i++) for(int j=i+1; j<=n; j++){
vec[rand()%k].push_back(Edge(i, j));
}
}
struct unionFind{
int par[5002];
void init(int n){
for(int i=1; i<=n; i++) par[i] = i;
}
int find(int x){
if(x==par[x]) return x;
return par[x] = find(par[x]);
}
void merge(int x, int y){
x=find(x), y=find(y);
par[x] = y;
}
} dsu;
vector<pair<int, int> > ans;
}
vector<pair<int,int> > Alice(){
init();
ll X = setN(n);
vector<int> v;
for(int d=0; d<k; d++) if((X>>d)&1) v.push_back(d);
dsu.init(n);
int pnt = 0, m = 0;
while(m < n-1){
int x = v[pnt];
while(!vec[x].empty()){
int a = vec[x].back().x, b = vec[x].back().y;
vec[x].pop_back();
if(dsu.find(a) == dsu.find(b)) continue;
dsu.merge(a, b), m++, ans.push_back(make_pair(a, b));
// printf("%d\n", m);
break;
}
pnt = (pnt + 1) % (int)v.size();
}
return ans;
}
#include "Bob.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace {
struct Edge{
int x, y;
Edge(){}
Edge(int x, int y): x(x), y(y){}
};
const int n = 5000, k = 60;
int where[5002][5002];
vector<Edge> vec[k];
void init(){
for(int i=1; i<=n; i++) for(int j=i+1; j<=n; j++){
int w = rand()%k;
vec[w].push_back(Edge(i, j));
where[i][j] = where[j][i] = w;
}
}
}
ll Bob(vector<pair<int,int>> V){
init();
ll X = 0;
for(auto [x, y]: V) X |= 1LL << where[x][y];
return X;
}
