#include "highway.h"
#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn=1e5, maxm=2e5;
int m, a, b, n;
vector < int > ms[maxn];
vector < int > ms1[maxn];
pair < int, int > edge[maxm];
vector < int > Q;
ll poc;
int nadji(int l, int r){
if(l==r-1){
return l;
}
int mid=(l+r)/2;
for(int i=l; i<mid; i++){
Q[i]=1;
}
ll val=ask(Q);
if(val>poc){
for(int i=l; i<mid; i++){
Q[i]=0;
}
return nadji(l, mid);
}
else{
return nadji(mid, r);
}
}
int dist[2][maxn];
void bfs(int x, int ind){
queue < int > q;
q.push(x);
dist[ind][x]=0;
while(!q.empty()){
x=q.front();
q.pop();
for(int i=0; i<(int)ms[x].size(); i++){
if(dist[ind][ms[x][i]]==-1){
dist[ind][ms[x][i]]=dist[ind][x]+1;
q.push(ms[x][i]);
}
}
}
}
int col[maxn];
vector < int > sta[maxn];
vector < int > sta1[maxn];
int bio[maxn];
void bfs1(int x){
queue < int > q;
q.push(x);
memset(bio, -1, sizeof(bio));
bio[x]=0;
while(!q.empty()){
x=q.front();
q.pop();
for(int i=0; i<(int)ms[x].size(); i++){
if(bio[ms[x][i]]==-1 && col[ms[x][i]]==col[x]){
bio[ms[x][i]]=bio[x]+1;
sta[x].push_back(ms[x][i]);
sta1[x].push_back(ms1[x][i]);
sta[ms[x][i]].push_back(x);
q.push(ms[x][i]);
}
}
}
}
vector < int > red;
void dfs(int x, int prosl){
for(int i=0; i<(int)sta[x].size(); i++){
if(sta[x][i]!=prosl){
red.push_back(sta1[x][i]);
dfs(sta[x][i], x);
}
}
}
ll maksi;
int rijesi(int l, int r){
if(l==r-1){
return l;
}
int mid=(l+r)/2;
for(int i=l; i<mid; i++){
if(red[i]==-1){
continue;
}
Q[red[i]]=1;
}
if(ask(Q)==maksi){
return rijesi(l, mid);
}
else{
return rijesi(mid, r);
}
}
void find_pair(int N, vector<int> u, vector<int> v, int A, int B) {
m = u.size();
n=N;
a=A;
b=B;
for(int i=0; i<m; i++){
edge[i]={u[i], v[i]};
ms[u[i]].push_back(v[i]);
ms[v[i]].push_back(u[i]);
ms1[u[i]].push_back(i);
ms1[v[i]].push_back(i);
}
Q.resize(m, 0);
poc=ask(Q);
int x=nadji(0, m);
memset(dist[0], -1, sizeof(dist[0]));
memset(dist[1], -1, sizeof(dist[1]));
bfs(edge[x].first, 0);
bfs(edge[x].second, 1);
for(int i=0; i<n; i++){
if(dist[0][i]<dist[1][i]){
col[i]=1;
}
}
red.push_back(-1);
bfs1(edge[x].first);
dfs(edge[x].first, -1);
for(int i=1; i<(int)red.size(); i++){
Q[red[i]]=1;
}
maksi=ask(Q);
for(int i=1; i<(int)red.size(); i++){
Q[red[i]]=0;
}
/* cout << "red ";
for(int i=0; i<(int)red.size(); i++){
cout << red[i] << ' ';
}
cout << endl;*/
int y=red[rijesi(0, red.size())];
int sol1, sol2;
if(y==-1){
sol1=edge[x].first;
}
else if(bio[edge[y].first]>bio[edge[y].second]){
sol1=edge[y].first;
}
else{
sol1=edge[y].second;
}
/* for(int i=0; i<n; i++){
sta[i].clear();
sta1[i].clear();
}*/
bfs1(edge[x].second);
red.clear();
red.push_back(-1);
dfs(edge[x].second, -1);
for(int i=1; i<(int)red.size(); i++){
Q[red[i]]=1;
}
maksi=ask(Q);
for(int i=1; i<(int)red.size(); i++){
Q[red[i]]=0;
}
/* cout << "red2 ";
for(int i=0; i<(int)red.size(); i++){
cout << red[i] << ' ';
}
cout << endl;*/
y=red[rijesi(0, red.size())];
if(y==-1){
sol2=edge[x].second;
}
else if(bio[edge[y].first]>bio[edge[y].second]){
sol2=edge[y].first;
}
else{
sol2=edge[y].second;
}
// cout << sol1 << ' ' << sol2 << endl;
answer(sol1, sol2);
}
