#include "highway.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 2e5 + 12;

vector<pair<int, int>> g[maxn];
ll d1[maxn], d2[maxn];
ll a, b;
int n, m;

vector<array<int, 3>> bfs(int v, ll d[]) {
    vector<array<int, 3>> res;
    for(int i = 0; i < n; i++) {
        if(d[i] >= 0) {
            d[i] = 1e18;
        }
    }

    d[v] = 0;
    queue<int> q;
    res.push_back({v, v, -1});
    q.push(v);
    while(q.size()) {
        int u = q.front();
        q.pop();
        for(auto [to, id] : g[u]) {
            if(d[to] > d[u] + 1) {
                q.push(to);
                d[to] = d[u] + 1;
                res.push_back({u, to, id});
            }
        }
    }

    return res;
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    n = N, m = (int)U.size();
    a = A, b = B;

    for(int i = 0; i < m; i++) {
        g[U[i]].push_back({V[i], i});
        g[V[i]].push_back({U[i], i});
    }

    int pos = -1;
    ll len = ask(vector<int> (m, 0));
    len /= a;
    for(int l = 0, r = m - 1; l <= r;) {
        int mid = (l + r) >> 1;
        vector<int> w(m, 0);
        for(int i = 0; i <= mid; i++) {
            w[i] = 1;
        }
        if(ask(w) > len * a) {
            pos = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }

    vector<int> ww(m, 0);
    ww[0] = 1;
    bfs(U[pos], d1);
    bfs(V[pos], d2);

    vector<int> s, t;
    for(int i = 0; i < n; i++) {
        if(d1[i] < d2[i]) {
            s.push_back(i);
            d2[i] = -1;
        }
        if(d2[i] < d1[i]) {
            t.push_back(i);
            d1[i] = -1;
        }
    }

    auto ord = bfs(U[pos], d1);
    auto orz = bfs(V[pos], d2);

    int u = -1, v = -1;
    for(int l = 0, r = (int)ord.size() - 1; l <= r;) {
        int mid = (l + r) >> 1;
        vector<int> w(m, 0);
        for(int i = 1; i < ord.size(); i++) {
            w[ord[i][2]] = (i > mid);
        }
        if(ask(w) == len * a) {
            u = ord[mid][1];
            r = mid - 1;
        }
        else l = mid + 1;
    }
    for(int l = 0, r = (int)orz.size() - 1; l <= r;) {
        int mid = (l + r) >> 1;
        vector<int> w(m, 0);
        for(int i = 1; i < orz.size(); i++) {
            w[orz[i][2]] = (i > mid);
        }
        if(ask(w) == len * a) {
            v = orz[mid][1];
            r = mid - 1;
        }
        else l = mid + 1;
    }

    answer(u, v);
}