#include <vector>
#include "Alice.h"
using namespace std;
vector<pair<int,int>> Alice()
{
vector<pair<int,int>> muchie;
long long x = setN(5000),val,cat,rest,U,i,prim;
val=x-1;
/// Simplu
if(val>=24995000)
{
U=val-24995000+1;
for(i=1;i<=5000;i++)
{
if(i == U)
continue;
muchie.push_back({U,i});
}
return muchie;
}
/// Dublu
rest=(val%5000)+1;
cat=val/5000;
vector<int> L;
for(i=1;i<=5000;i++)
{
if(i!=rest)
L.push_back(i);
}
prim=L[cat];
vector<int> L2;
for(i=0;i<4999;i++)
{
if(L[i]!=prim)
L2.push_back(L[i]);
}
muchie.push_back({U,prim});
for(i=0;i<2499;i++)
muchie.push_back({U,L2[i]});
for(i=2499;i<4998;i++)
muchie.push_back({prim,L2[i]});
return muchie;
}
#include <vector>
#include "Bob.h"
using namespace std;
long long Bob(vector<pair<int,int>> V_edges)
{
int i,V_idx,V_nod;
vector<int> deg(5005, 0);
for(auto edge : V_edges)
{
deg[edge.first]++;
deg[edge.second]++;
}
vector<int> candidates_U;
for(i=1;i<=5000;i++)
{
if(deg[i]>=2)
candidates_U.push_back(i);
}
for(int U:candidates_U)
{
vector<int> L,L2;
for(i=1;i<=5000;i++)
{
if(i!=U)
L.push_back(i);
}
for(V_idx=0;V_idx<4999;V_idx++)
{
V_nod = L[V_idx];
L2.clear();
for(i=0;i<4999;i++)
{
if(L[i]!=V_nod)
L2.push_back(L[i]);
}
vector<int> parent(5005, 0);
parent[V_nod] = 1;
for(i=0;i<2499;i++)
parent[L2[i]] = 1;
for(i=2499;i<4998;i++)
parent[L2[i]] = 2;
bool is_match=true;
for(auto [u,v] : V_edges)
{
bool covered = false;
if(u == U && parent[v] == 1)
covered = true;
else if(v == U && parent[u] == 1)
covered = true;
else if(u == V_nod && parent[v] == 2)
covered = true;
else if(v == V_nod && parent[u] == 2)
covered = true;
if(covered==false)
{
is_match = false;
break;
}
}
if(is_match==true)
{
return (long long)V_idx * 5000 + (U - 1) + 1;
}
}
}
int maxi;
maxi=1;
for(i=1;i<=5000;i++)
{
if(deg[i]>deg[maxi])
maxi=i;
}
return 24995000LL+maxi;
}
