#include <vector>
#include "Alice.h"
#include <algorithm>
#include <random>
#include <climits>

using namespace std;

std::vector<std::pair<int,int>> Alice(){
    long long x = setN(5000);
    vector<pair<int, int>> edges;
    for(int i = 1; i <= 4999; i++)
        edges.emplace_back(x % i + 1, i + 1);
    return edges;
}

#include <vector>
#include "Bob.h"
#include <iostream>

using namespace std;

pair<pair<long long, long long>, long long> ext_gcd(int a, int b){
    if(a < b) swap(a, b);
    if(b == 0) return {{1, 0}, a};
    auto p = ext_gcd(b, a % b);
    return make_pair(make_pair(p.first.second, p.first.first - (a / b) * p.first.second), p.second);
}

long long find(pair<long long, long long> a, pair<long long, long long> q){
    int a1 = a.second, a2 = q.second, r1 = a.first, r2 = q.first;
    auto p = ext_gcd(a1, a2);
    return a1 * p.first.first * (r2 - r1) + r1;
}

long long solve(vector<pair<int, int>> v){
    while((int)v.size() > 2){
        auto p = v[v.size() - 2], q = v[v.size() - 1];
        v.pop_back(), v.pop_back();
        long long x = find(p, q);
        v.emplace_back(x, p.second * q.second);
    }
    return find(v[0], v[1]);
}

long long Bob(std::vector<std::pair<int,int>> V){
    vector<pair<int, int>> edges;
    for(int i = 1; i < V.size() && edges.size() < 5; i++)
        edges.emplace_back(V[i].first - 1, V[i].second - 1);
    long long res = solve(edges);
    for(long long x = res; x <= (int)1e18; x += res){
        bool F = false;
        for(int i = 1; i < V.size(); i++){
            if(x % (V[i].second - 1) != (V[i].first - 1)){
                F = true;
                break;
            }
        }
        if(!F) return x;
    }
    return -1;
}