#include "souvenirs.h"
#include "bits/stdc++.h"
using namespace std;
// #include "atcoder/"
// using namespace atcoder;
using ll = long long;
using vi = vector<int>;
using dt = pair<vector<int>, ll>;
#define eb emplace_back
#define fr first
#define sc second
#define mp make_pair
pair<vector<int>, ll> qry(ll M) {
// printf("querying %lld\n", M);
return transaction(M);
}
void buy_souvenirs(int n, long long m) {
dt a[n];
ll b[n];
b[1] = m - 1;
a[1] = qry(b[1]);
for(int i = 2; i < n; ++i) {
b[i] = (b[i - 1] - a[i - 1].sc + (ll)(a[i - 1].fr.size()) - 1) / ((ll)(a[i - 1].fr.size())) - 1;
// if(a[i - 1].fr.size() == 1) --b[i];
a[i] = qry(b[i]);
}
int p[n];
p[0] = m;
p[n - 1] = b[n - 1] - a[n - 1].sc;
for(int i = n - 2; i > 0; --i) {
vi v = a[i].fr;
ll r = a[i].sc;
ll c = b[i];
p[i] = c - r;
for(int x : v) {
if(x != i) {
p[i] -= p[x];
}
}
}
int cnt[n] = {};
for(int i = 1; i < n; ++i) {
for(int x : a[i].fr) ++cnt[x];
}
// for(int v : cnt) printf("%d ", v);
// printf("\n");
for(int i = 1; i < n; ++i) {
while(cnt[i] < i) {
qry(p[i]);
++cnt[i];
}
}
}
