#include <bits/stdc++.h>
#include "Alice.h"
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
// you may define some global variables, but it does not work if you try to transfer any information from function Alice() to function Bob() through these variables.
// you had better not use the same global variables in function Alice() and in function Bob().
std::vector<std::pair<int,int>> Alice(){
const int num_cmps = 25;
int n = 5000;
const int mega_root = 3541;
// add your code here
int cmp_size = (n - 1) / num_cmps;
//n = cmp_size * num_cmps + 1;
vector<pii> out;
/*mt19937_64 rand(53);
ll mask = rand() % (1LL << num_cmps);
ll x = setN(n) ^ mask;
vector<int> all_nodes(n);
iota(all_nodes.begin(), all_nodes.end(), 1);
all_nodes.erase(all_nodes.begin() + mega_root - 1);
shuffle(all_nodes.begin(), all_nodes.end(), rand);
for (int cmp = 0; cmp < num_cmps; cmp++) {
//cout << all_nodes[cmp * cmp_size] << "\n";
out.emplace_back(all_nodes[cmp * cmp_size], mega_root);
if ((1LL << cmp) & x) {
for (int i = 1; i < cmp_size; i++)
out.emplace_back(all_nodes[cmp * cmp_size + i], all_nodes[cmp * cmp_size + i - 1]);
} else {
for (int i = 1; i < cmp_size; i++)
out.emplace_back(all_nodes[cmp * cmp_size + i], all_nodes[cmp * cmp_size]);
}
}*/
ll x = setN(n);
for (int i = 1; i <= n; i++) {
if (i != x)
out.emplace_back(i, x);
}
return out;
}
#include <bits/stdc++.h>
#include "Bob.h"
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int num_cmps = 25;
int n = 5000;
const int mega_root = 3541;
// you may define some global variables, but it does not work if you try to transfer any information from function Alice() to function Bob() through these variables.
// you had better not use the same global variables in function Alice() and in function Bob().
long long Bob(std::vector<std::pair<int,int>> V){
// add your code here
/*int cmp_size = (n - 1) / num_cmps;
n = cmp_size * num_cmps + 1;
mt19937_64 rand(53);
ll mask = rand() % (1LL << num_cmps);
ll x = 0;
vector<pii> out;
vector<int> all_nodes(n);
iota(all_nodes.begin(), all_nodes.end(), 1);
all_nodes.erase(all_nodes.begin() + mega_root - 1);
shuffle(all_nodes.begin(), all_nodes.end(), rand);
vector<int> what_cmp(n);*/
int n = 5000;
vector<int> deg(n + 1);
for (auto [x, y] : V) {
deg[x]++;
deg[y]++;
}
/*for (int cmp = 0; cmp < num_cmps; cmp++)
{
if (deg[all_nodes[cmp * cmp_size]] == 1 || deg[all_nodes[cmp * cmp_size]] == 2)
x += (1LL << cmp);
}
x ^= mask;*/
int x = max_element(deg.begin(), deg.end()) - deg.begin();
return x;
}
/*
3428
4837
3077
897
3562
4043
1443
1582
2142
572
281
4127
1550
2518
4156
2166
3251
118
4957
1408
1892
554
1734
3734
661
4976
*/
