#include <bits/stdc++.h>
using namespace std;
int count(const unordered_set<int> &a, const unordered_set<int> &b) {
    int r = 0;
    for (int x : a) {
        r += b.count(x);
    }
    return r;
}

void better(int& r, int &num, int id, int count) {
    if (r < 0  or (num < count or   ((num == count) && (r > id)))) {
        r = id;
        num = count;
    }
}

vector<int> getRecommendedFriends(int n, const vector<vector<int>> friendships) {
     vector<int> r(n, -1), num(n, 0);
    vector<unordered_set<int>> con(n);
    for (const auto& v : friendships) {
        con[v[0]].insert(v[1]);
        con[v[1]].insert(v[0]);
    }
   

    for (int i = 0; i<n; ++i) {
        for (auto t1 = con[i].begin(); t1 != con[i].end(); ++t1) {
            for (auto t2 = next(t1); t2 != con[i].end(); ++t2) {
               
                if (con[*t1].count(*t2) == 0) {
                    const int x = count(con[*t1], con[*t2]);
                    better(r[*t1], num[*t1], *t2, x);
                    better(r[*t2], num[*t2], *t1, x);
                }
                
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        if (r[i] < 0) {
            int j = 0;
            for (; j < n && (j == i) || con[i].count(j); ++j);
            if (j < n) {
                r[i] = j;
            }
        }
    
    }
    return r;
} 

class Solution {
public:
    vector<int> countServers(int n, vector<vector<int>>& logs, int x, vector<int>& queries) {
        sort(logs.begin(), logs.end(), [](const auto& a, const auto& b) {
            return a[1] < b[1];
        });
        int m = queries.size();
        vector<pair<int, int>> qs(m);
        for (int i = 0; i < m; ++i) {
            qs[i] = {queries[i], i};
        }
        sort(qs.begin(), qs.end());
        unordered_map<int, int> cnt;
        vector<int> ans(m);
        int j = 0, k = 0;
        for (auto& [r, i] : qs) {
            int l = r - x;
            while (k < logs.size() && logs[k][1] <= r) {
                ++cnt[logs[k++][0]];
            }
            while (j < logs.size() && logs[j][1] < l) {
                if (--cnt[logs[j][0]] == 0) {
                    cnt.erase(logs[j][0]);
                }
                ++j;
            }
            ans[i] = n - cnt.size();
        }
        return ans;
    }
};

#include <bits/stdc++.h>
using namespace std;
long long getMaxReliability(int maxConnections, int gnodes, vector<int> g_from, vector<int> g_to, vector<int> g_weight) {
    vector<vector<pair<int, int>>> adj(gnodes);

    for (int i = 0; i < gnodes - 1; ++i) {
        adj[g_from[i]].emplace_back(g_to[i], g_weight[i]);
        adj[g_to[i]].emplace_back(g_from[i], g_weight[i]);
    }

    function<array<long long, 2>(int, int)> dfs = [&](int cur, int parent) {
        array<long long, 2> ans{};
        vector<long long> take, skip, diff;

        for (auto& [next, w] : adj[cur]) {
            if (parent != next) {
                auto [not_full, full] = dfs(next, cur);
                take.push_back(not_full + w);
                skip.push_back(full);
                diff.push_back(take.back() - skip.back());
            }
        }

        int n = int(diff.size());
        nth_element(diff.begin(), diff.begin() + maxConnections - 1, diff.end(), greater<>());
        ans[0] = accumulate(diff.begin(), diff.begin() + min(maxConnections, n), 0LL) + accumulate(skip.begin(), skip.end(), 0LL);
        if (n && n >= maxConnections) {
            ans[1] = ans[0];
            ans[0] -= *min_element(diff.begin(), diff.begin() + maxConnections);
        }

        return ans;
    };
    auto ans = dfs(0, -1);
   // cout << "DFS Result - Not Full: " << ans[0] << ", Full: " << ans[1] << endl; 
    return max(ans[0], ans[1]);
}

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int>& err, int p, int q) {
    make_heap(err.begin(), err.end());
    pop_heap(err.begin(), err.end());
    int base_line = 0;
    int operations = 0;
    while (err.back() > base_line) {
        base_line += q;
        int max_err = err.back();
        err.pop_back();
        err.push_back(max_err - (p - q));
        push_heap(err.begin(), err.end());
        operations += 1;
        pop_heap(err.begin(), err.end());
    }
    return operations;
}