#include <vector>
#include "Alice.h"
// 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().
#include <bits/stdc++.h>
using namespace std;
#define int long long
namespace Alice_solver{
const int BIT=64;
int c[100][100];
vector<int> encode(int x){
vector<int> ans(BIT);
for (int i=0, rem=BIT/2; i<BIT; ++i){
if (x>=c[BIT-i-1][rem-1]){
x-=c[BIT-i-1][rem-1];
--rem;
ans[i]=1;
}
}
return ans;
}
int decode(vector<int> v){
int ans=0;
for (int i=0, rem=BIT/2; i<BIT; ++i){
if (v[i]){
ans+=c[BIT-i-1][rem-1];
--rem;
}
}
return ans;
}
int mp[5000], rmp[5000];
mt19937_64 rng(69420);
int SUS;
void precalc(){
for (int i=0; i<=BIT; ++i) c[i][0]=c[i][i]=1;
for (int i=1; i<=BIT; ++i){
for (int j=1; j<i; ++j) c[i][j]=c[i-1][j-1]+c[i-1][j];
}
iota(mp, mp+5000, 0);
shuffle(mp, mp+5000, rng);
for (int i=0; i<5000; ++i) rmp[mp[i]]=i;
SUS=uniform_int_distribution<int>(0, 1ll<<59)(rng);
}
vector<pair<int32_t, int32_t>> solve(){
precalc();
long long x=setN(5000); x^=SUS;
vector<int> v=encode(x);
for (int i:v) cerr << i;
cerr << endl;
vector<pair<int32_t, int32_t>> ans;
for (int i=0; i<5000/(BIT+2)*(BIT+2); i+=BIT+2){
for (int j=0; j<BIT; ++j){
int t1=uniform_int_distribution<int>(5000/(BIT+2)*(BIT+2), 4999)(rng);
int t2=t1;
while (t1==t2) t2=uniform_int_distribution<int>(5000/(BIT+2)*(BIT+2), 4999)(rng);
if (v[j]){
ans.emplace_back(i+j, t1);
}else{
ans.emplace_back(i+j, t2);
}
}
int t=uniform_int_distribution<int>(5000/(BIT+2)*(BIT+2), 4999)(rng);
ans.emplace_back(t, i+BIT);
ans.emplace_back(t, i+BIT+1);
}
for (int i=5000/(BIT+2)*(BIT+2)+1; i<5000; ++i) ans.emplace_back(i-1, i);
for (auto &i:ans) i.first=mp[i.first]+1, i.second=mp[i.second]+1;
return ans;
}
}
vector<pair<int32_t,int32_t>> Alice(){
// add your code here
// change below into your code
return Alice_solver::solve();
}
#include <vector>
#include "Bob.h"
// 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().
#include <bits/stdc++.h>
using namespace std;
#define int long long
namespace Bob_solver{
const int BIT=64;
int c[100][100];
vector<int> encode(int x){
vector<int> ans(BIT);
for (int i=0, rem=BIT/2; i<BIT; ++i){
if (x>=c[BIT-i-1][rem-1]){
x-=c[BIT-i-1][rem-1];
--rem;
ans[i]=1;
}
}
return ans;
}
int decode(vector<int> v){
int ans=0;
for (int i=0, rem=BIT/2; i<BIT; ++i){
if (v[i]){
ans+=c[BIT-i-1][rem-1];
--rem;
}
}
return ans;
}
int mp[5000], rmp[5000];
mt19937_64 rng(69420);
int SUS;
void precalc(){
for (int i=0; i<=BIT; ++i) c[i][0]=c[i][i]=1;
for (int i=1; i<=BIT; ++i){
for (int j=1; j<i; ++j) c[i][j]=c[i-1][j-1]+c[i-1][j];
}
iota(mp, mp+5000, 0);
shuffle(mp, mp+5000, rng);
for (int i=0; i<5000; ++i) rmp[mp[i]]=i;
SUS=uniform_int_distribution<int>(0, 1ll<<59)(rng);
}
bool adj[5000][5000];
int solve(vector<pair<int32_t, int32_t>> edge){
precalc();
for (auto &i:edge) i.first=rmp[i.first-1], i.second=rmp[i.second-1], adj[i.first][i.second]=adj[i.second][i.first]=1;
vector<int> v(BIT);
for (int i=0; i<5000/(BIT+2)*(BIT+2); i+=BIT+2){
for (int j=0; j<BIT; ++j){
int t1=uniform_int_distribution<int>(5000/(BIT+2)*(BIT+2), 4999)(rng);
int t2=t1;
while (t1==t2) t2=uniform_int_distribution<int>(5000/(BIT+2)*(BIT+2), 4999)(rng);
if (adj[i+j][t1]) v[j]=1;
}
int t=uniform_int_distribution<int>(5000/(BIT+2)*(BIT+2), 4999)(rng);
}
for (int i:v) cerr << i;
cerr << endl;
return decode(v)^SUS;
}
}
long long Bob(vector<pair<int32_t,int32_t>> V){
// add your code here
// return 3; // change this into your code
return Bob_solver::solve(V);
}
