#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 1e5 + 5;
ll n, m, d[NMAX], cost;
vector<pair<int, int>> adj[NMAX];
vector<int> A[2];
/*
ll ask(vector<int> w){
cout << "query : ";
for(int i = 0; i < m; i++) cout << w[i] << ' ';
cout << endl;
ll x;
cin >> x;
return x;
}
void answer(int s, int t){
cout << s << ' ' << t << '\n';
return;
}
*/
void find_pair(int n_, vector<int> U, std::vector<int> V, int a, int b) {
n = n_; m = U.size();
for(int i = 0; i < m; i++){
adj[U[i]].emplace_back(V[i], i);
adj[V[i]].emplace_back(U[i], i);
}
cost = ask(vector<int>(m));
int l = 0, r = m - 1, mid;
while(l < r){
mid = (l + r) / 2;
vector<int> w(m);
fill(w.begin(), w.begin() + mid + 1, 1);
if(ask(w) > cost) r = mid;
else l = mid + 1;
}
int u[2] = {U[l], V[l]};
memset(d, 0x3f, sizeof(d));
d[u[0]] = d[u[1]] = 1;
queue<pair<int, int>> q;
q.emplace(u[0], 0); q.emplace(u[1], 1);
while(q.size()){
auto[x, p] = q.front(); q.pop();
A[p].emplace_back(x);
for(auto&[nx, e] : adj[x])
if(d[x] + 1 < d[nx]){
d[nx] = d[x] + 1;
q.emplace(nx, p);
}
}
int v[2];
for(int t = 0; t < 2; t++){
int l = 0, r = A[t].size() - 1, mid;
while(l < r){
mid = (l + r) / 2;
vector<int> w(m);
for(int i = mid + 1; i <= r; i++)
for(auto&[j, e] : adj[A[t][i]]) w[e] = 1;
if(ask(w) > cost) l = mid + 1;
else r = mid;
}
v[t] = A[t][l];
}
answer(v[0], v[1]);
return;
}
/*
int main(void){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, m, a, b, s, t;
cin >> n >> m >> a >> b >> s >> t;
vector<int> U(m), V(m);
for(int i = 0; i < m; i++) cin >> U[i] >> V[i];
find_pair(n, U, V, a, b);
return 0;
}
*/
