#include <vector>
#include <bits/stdc++.h>
#include "Alice.h"
using namespace std;
using ll=int;
// 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(){
// add your code here
// change below into your code
std::vector<std::pair<int,int>> ret;
long long x = setN(5000);
if(x<=5000)
{
for(int i=1;i<=5000;i++)
{
if(i==x)continue;
ret.push_back({x,i});
}
return ret;
}
ll a,b,c;
a=(x-2)/4999;
b=(x-2)%4999+1;
b+=(b>=a);
c=(a+b);
if(c>5000)
c-=5000;
cerr << a << ',' << b << '\n';
for(int i=1;i<=1667;i++)
{
if(i==a || i==b || i==c)
continue;
ret.push_back({i,a});
}
for(int i=1668;i<=3334;i++)
{
if(i==a || i==b || i==c)
continue;
ret.push_back({i,b});
}
for(int i=3335;i<=5000;i++)
{
if(i==a || i==b || i==c)
continue;
ret.push_back({i,c});
}
if(a!=b)
ret.push_back({a,b});
if(b!=c)
ret.push_back({b,c});
return ret;
}
#include <vector>
#include <bits/stdc++.h>
#include "Bob.h"
using namespace std;
using ll=int;
// 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().
bool checkIfDumbCase(std::vector<std::pair<int,int>> &adj)
{
vector<int> degree(5001,0);
for(auto edge:adj)
{
degree[edge.first]+=1;
degree[edge.second]+=1;
}
int cnt=0;
for(int i=1;i<=5000;i++)
cnt+=degree[i]>1;
return cnt==1;
}
long long Bob(std::vector<std::pair<int,int>> adj){
// add your code here
vector<int> degree(5001,0);
for(auto edge:adj)
{
degree[edge.first]+=1;
degree[edge.second]+=1;
}
if(checkIfDumbCase(adj))
{
for(int i=1;i<=5000;i++)
if(degree[i]>1)
return i;
}
ll a=-1,b=-1,c=-1;
vector<ll> candidateA(5001,0);
vector<ll> candidateB(5001,0);
vector<ll> candidateC(5001,0);
int u,v;
for(auto edge:adj)
{
u=edge.first;
v=edge.second;
if(1<=u && u<=1667)
candidateA[v]+=1;
if(1667<=u && u<=3334)
candidateB[v]+=1;
if(3335<=u && u<=5000)
candidateC[v]+=1;
swap(u,v);
if(1<=u && u<=1667)
candidateA[v]+=1;
if(1667<=u && u<=3334)
candidateB[v]+=1;
if(3335<=u && u<=5000)
candidateC[v]+=1;
}
for(int i=1;i<=5000;i++)
{
if(candidateA[i]>5)
a=i;
}
for(int i=1;i<=5000;i++)
{
if(candidateB[i]>5)
b=i;
}
for(int i=1;i<=5000;i++)
{
if(candidateC[i]>5)
c=i;
}
if(a==-1)
a=(c<b)*5000+c-b;
if(b==-1)
b=(c<a)*5000+c-a;
cerr << a << ',' << b << '\n';
ll ans=5001;
ans+=(a-1)*4999;
ans+=(b-(b>=a))-1;
return ans; // change this into your code
}
