#include <bits/stdc++.h>
using namespace std;
#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().
vector<pair<int,int>> Alice(){
// add your code here
// change below into your code
long long x = setN(5000);
vector<pair<int,int>>tree;
for(int i = 1;i<5000;i++){
tree.push_back({i,x%i});
}
for(pair<int,int>&p:tree){
p.first++;
p.second++;
}
return tree;
}
#include <bits/stdc++.h>
using namespace std;
#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().
long long po(long long a, long long p, long long mod){
long long x = a;
long long ans = 1;
for(int i = 0;i<32;i++){
if((1<<i)&p){
ans*=x;
ans%=mod;
}
x*=x;
x%=mod;
}
return ans;
}
int totient(int a){
int ans = 0;
for(int i = 1;i<=a;i++){
if(gcd(a,i)==1){
ans++;
}
}
return ans;
}
long long Bob(vector<pair<int,int>> V){
// add your code here
for(pair<int,int>&p:V){
p.first--;
p.second--;
if(p.first<p.second)
swap(p.first,p.second);
}
sort(V.begin(),V.end());
reverse(V.begin(),V.end());
map<long long,vector<pair<int,int>>>mp;
vector<pair<int,int>>doable;
for(pair<int,int>p:V){
mp[p.first].push_back(p);
int a = p.first;
int m = p.second;
map<long long,vector<pair<int,int>>>temp;
for(pair<long long,vector<pair<int,int>>>p:mp){
if(gcd(p.first,a)==1){
///can push into this
p.second.push_back({a,m});
if(((__int128)(a))*(p.first)>=1e18){
//found
doable=p.second;
break;
}
else{
temp[a*(p.first)]=p.second;
}
}
}
for(pair<long long,vector<pair<int,int>>>p:temp){
mp[p.first]=p.second;
}
if(doable.size())
break;
}
assert(doable.size());
//doable found
__int128 prod = 1;
for(pair<int,int>p:doable){
prod*=p.first;
}
__int128 ans = 0;
for(pair<int,int>p1:doable){
__int128 rem = (prod)/p1.first;
int tot = totient(p1.first);
assert((rem*po(rem%p1.first,tot-1,p1.first)%p1.first)==1);
ans+=((1LL*p1.second*rem*po(rem%p1.first,tot-1,p1.first)))%prod;
__int128 temp = ((1LL*p1.second*rem*po(rem%p1.first,tot-1,p1.first)))%prod;
for(pair<int,int>p2:doable){
if(p2.first==p1.first)
continue;
assert(temp%p2.first==0);
}
assert(temp%(p1.first)==p1.second);
ans%=prod;
}
long long fin = ans;
return fin; // change this into your code
}
