#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
using namespace std;
long long setN(int n);
std::vector<std::pair<int,int>> Alice() {
int n = 3000;
long long x = setN(n);
vector<pair<int, int>> edge;
for (int u=1; u<n; u++) {
int v = x % u;
edge.push_back({v+1, u+1});
}
return edge;
}
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#define ff first
#define ss second
using namespace std;
using i128 = __int128_t;
namespace {
pair<i128, i128> exgcd(i128 x, i128 y) {
if (y == 0) return {1, 0};
i128 q = x / y, r = x % y;
auto [c, d] = exgcd(y, r);
return {d, c - d * q};
}
pair<i128, i128> crt(pair<i128, i128> p1, pair<i128, i128> p2) {
auto [r1, m1] = p1;
auto [r2, m2] = p2;
if (m1 == 0 || m2 == 0) return {0, 0};
i128 g = gcd(m1, m2);
if ((r2 - r1) % g != 0) return {0, 0};
auto [a, b] = exgcd(m1, m2);
i128 w = (r2 - r1) / g;
i128 M = lcm(m1, m2);
i128 R = (w * a % M * m1 % M + r1) % M;
return {(R % M + M) % M, M};
}
}
long long Bob(std::vector<std::pair<int,int>> V) {
pair<i128, i128> ans = {0, 1};
for (auto [v, u]: V) {
if (v > u) swap(u, v);
ans = crt(ans, {v-1, u-1});
if (ans.second > 1e18) break;
}
return ans.first;
}
