#include <vector>
#include "Alice.h"
#include "bits/stdc++.h"
#define dbg(X) cerr<<#X<<": "<<X<<endl;
#define fi first
#define sc second
#define here cerr<<"=====================================\n"
#define pb push_back
#define si(a_) (ll)(a_.size())
#define ceri(a_,l_,r_) {for(ll i_ = l_;i_<=r_;i_++) cerr<<a_[i_]<< " ";cerr<<endl;}
using namespace std;
using ll = int;
using pll = pair<ll,ll>;
vector<pll> ans;
void upd(vector<pll> &v){
for(auto &it : v) it.fi++,it.sc++;
}
std::vector<std::pair<int,int>> Alice(){
ll n = 5000;
long long x = setN(n);
for(ll i = 1;i<=n;i++){
if(i^x) ans.pb({i,x});
}
return ans;
x--;
ll a = x/n;
ll b = x%n;
a++;
b++;
ll c = (a+b)/2;
//cerr<<"abc: "<<a<< " "<<b<< " "<<c<<endl;
if(a==b){
dbg(si(ans));
return ans;
}
if(c==a||c==b){
if(min(a,b)>2){
c = a>b?1:2;
}else{
c = a>b?4999:5000;
}
}
ans.pb({a,c});
ans.pb({b,c});
vector<ll> v;
for(ll i = 1;i<=n;i++){
if(i!=a&&i!=b&&i!=c) v.pb(i);
}
ll l = si(v)/3,r = 2*si(v)/3;
for(ll i = 0;i<l;i++) ans.pb({a,v[i]});
for(ll i = l;i<r;i++) ans.pb({c,v[i]});
for(ll i = r;i<si(v);i++) ans.pb({b,v[i]});
//dbg(si(v));
return ans;
}
#include <vector>
#include "Bob.h"
#include "bits/stdc++.h"
#define dbg(X) cerr<<#X<<": "<<X<<endl;
#define fi first
#define sc second
#define here cerr<<"=====================================\n"
#define pb push_back
#define si(a_) (ll)(a_.size())
#define all(a_) a_.begin(),a_.end()
#define ceri(a_,l_,r_) {for(ll i_ = l_;i_<=r_;i_++) cerr<<a_[i_]<< " ";cerr<<endl;}
using namespace std;
using ll = int;
using pll = pair<ll,ll>;
ll n;
const ll maxn = 5005;
ll deg[maxn];
bool tu[maxn];
pll vals[maxn];
vector<ll> g[maxn];
ll cnt[maxn];
long long Bob(std::vector<std::pair<int,int>> V){
n = 5000;
for(pll p : V) deg[p.fi]++,deg[p.sc]++,g[p.fi].pb(p.sc),g[p.sc].pb(p.fi);
vector<ll> w;
for(ll i = 1;i<=n;i++){
if(deg[i]>1) w.pb(i);
}
// dbg(si(w));
for(ll x : w) tu[x] = 1;
// ceri(w,0,si(w)-1);
for(ll i = 0;i<n;i++){
if(si(g[i])==0) vals[i] = {-1,-1};
else{
vals[i] = {n+1,-1};
for(ll x : g[i]){
if(tu[x]) continue;
vals[i].fi = min(vals[i].fi,x);
vals[i].sc = max(vals[i].sc,x);
}
}
}
if(si(w)==1){
return w[0];
}
for(ll x : w){
// dbg(x);
// dbg(vals[x].fi);
//dbg(vals[x].sc);
}
sort(all(w),[](ll i,ll j){
return vals[i]<vals[j];
});
if(si(w)==3){
w[0]--; w[2]--;
return 5000*w[0]+w[2]+1;
}
if(si(w)==2){
bool tua = 1;
for(ll x : g[w[1]]) if(x>=2*n/3) tua = 0;
ll a,b;
if(tua){
a = w[0];
if(w[1]<w[0]){
if(w[1]&1) b = a-1;
else b = a+1;
}else{
}
}
a--; b--;
return a*5000+b+1;
}
}
