#include"Alice.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
namespace A{
const ll mod=4096;
ll n,i,j,k,l,r,x,y,z,w,s,t,a[1100000],b[1100000],adj[5500][5500],c[1100000],d[1100000],h[1100000],e,m,perm[1100000];
vector<ll> v[1100000];
vector<pair<ll,ll>> u;
vector<pair<int,int>> p;
void link(ll x,ll y,ll z)
{
ll i;
for(i=y;i<=z;i++)
{
perm[i]=x;
if(adj[x][i]==0)
{
adj[x][i]=1;
adj[i][x]=1;
}
}
}
pair<ll,ll> f(ll x,ll y)
{
//printf("%lld(%lld)\n",ll(x),y);
c[x]=1;
ll i,mn=100000,mx=0;
pair<ll,ll> p;
for(i=0;i<h[x];i++)
{
if(v[x][i]==y)
continue;
p=f(v[x][i],x);
mn=min(mn,p.first);
mx=max(mx,p.second);
}
if(h[x]<=1)
{
mn=min(mn,x);
mx=max(mx,x);
}
return {mn,mx};
}
void Clear()
{
ll i;
for(i=1;i<=4991;i++)
{
v[i].clear();
h[i]=0;
b[i]=0;
a[i]=0;
c[i]=0;
d[i]=0;
perm[i]=0;
}
for(i=1;i<=4991;i++)
for(j=1;j<=4991;j++)
{
adj[i][j]=0;
}
}
vector<pair<int,int>> Alice()
{
for(i=1;i<=4991;i++)
adj[i][i]=1;
k=setN(4991);
i=1;
while(k>0)
{
a[i]=k%mod;
k/=mod;
i++;
}
for(i=1;i<=31;i++)
{
x=i;
j=1;
while(x>0)
{
if(x&1)
{
b[i]^=a[j];
}
x>>=1;
j++;
}
b[i]++;
}
for(i=1;i<=31;i++)
{
if(i!=31)
link(b[i],(i-1)*161+1,i*161);
else
{
link(b[i],(i-1)*161+1,4991);
}
}
n=4991;
for(i=1;i<=n;i++)
{
if(c[i]==2)
continue;
x=i;
y=0;
while(1)
{
c[x]=1;
y=x;
x=perm[x];
if(c[x]==2)
break;
if(c[x]==1)
{
if(x==y)
break;
adj[x][y]=0;
adj[y][x]=0;
break;
}
}
x=i;
while(1)
{
if(c[x]==2)
break;
c[x]=2;
x=perm[x];
}
}
for(i=1;i<=n;i++)
{
c[i]=0;
}
for(i=1;i<=n;i++)
{
for(j=1;j<i;j++)
{
if(adj[i][j]==1)
{
v[i].push_back(j);
v[j].push_back(i);
h[i]++;
h[j]++;
p.push_back({i,j});
}
}
}
for(i=1;i<=n;i++)
{
if(c[i]==0)
{
u.push_back(f(i,0));
}
}
for(i=0;i<u.size()-1;i++)
{
x=u[i].first;
y=u[i+1].second;
v[x].push_back(y);
v[y].push_back(x);
h[x]++;
h[y]++;
p.push_back({x,y});
}
return p;
}
};
vector<pair<int,int>> Alice()
{
return A::Alice();
}
#include"Bob.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
namespace B{
const ll mod=4096;
ll n,i,j,k,l,r,x,y,z,w,s,t,a[1100000],b[1100000],adj[5500][5500],c[1100000],d[1100000],h[1100000],e,m,perm[1100000];
vector<ll> v[1100000];
vector<pair<ll,ll>> u,p;
void link(ll x,ll y,ll z)
{
ll i;
for(i=y;i<=z;i++)
{
perm[i]=x;
if(adj[x][i]==0)
{
adj[x][i]=1;
adj[i][x]=1;
}
}
}
pair<ll,ll> f(ll x,ll y)
{
//printf("%lld(%lld)\n",ll(x),y);
c[x]=1;
ll i,mn=100000,mx=0;
pair<ll,ll> p;
for(i=0;i<h[x];i++)
{
if(v[x][i]==y)
continue;
p=f(v[x][i],x);
mn=min(mn,p.first);
mx=max(mx,p.second);
}
if(h[x]<=1)
{
mn=min(mn,x);
mx=max(mx,x);
}
return {mn,mx};
}
void Clear()
{
ll i;
for(i=1;i<=4991;i++)
{
v[i].clear();
h[i]=0;
b[i]=0;
a[i]=0;
c[i]=0;
d[i]=0;
perm[i]=0;
}
for(i=1;i<=4991;i++)
for(j=1;j<=4991;j++)
{
adj[i][j]=0;
}
}
ll Bob(vector<pair<int,int>> V)
{
Clear();
m=V.size();
for(i=1;i<=m;i++)
{
x=V[i-1].first;
y=V[i-1].second;
v[x].push_back(y);
v[y].push_back(x);
h[x]++;
h[y]++;
}
n=4991;
for(e=1;e<=31;e++)
{
if(e!=31)
{
l=(e-1)*161+1;
r=e*161;
}
else
{
l=(e-1)*161+1;
r=4991;
}
for(i=1;i<=n;i++)
{
if(h[i]>=2)
{
//printf("(%lld)\n",i);
s=0;
for(j=0;j<h[i];j++)
{
if(l<=v[i][j]&&r>=v[i][j])
s++;
}
if(s>=2)
{
b[e]=i-1;
//printf("%lld %lld\n",e,i-1);
break;
}
}
if(i==n)
{
b[e]=-1;
}
}
}
b[0]=0;
d[1]=1;
d[2]=2;
d[4]=3;
d[8]=4;
d[16]=5;
for(i=0;i<=31;i++)
{
for(j=0;j<=31;j++)
{
if((i|j)==j&&d[(j-i)]!=0)
{
if(b[i]!=-1&&b[j]!=-1)
{
a[d[j-i]]=b[i]^b[j];
}
}
}
}
s=0;
for(i=5;i>=1;i--)
{
s=s*mod+a[i];
}
return s;
}
};
ll Bob(vector<pair<int,int>> V)
{
return B::Bob(V);
}
