#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef long long ll;
const int len = 2e5+5;
ii edge[len];
int n, m, vis[len];
ll dis;
vector<ii> adj[len];
void find_bridge(int &x, int &y){
int l = 0, r = m-1;
while (l < r){
int mid = (l+r)/2;
vector<int> temp(m, 0);
for (int j = 0; j <= mid; j++)
temp[j] = 1;
if (ask(temp) > dis)
r = mid;
else
l = mid+1;
}
x = edge[l].fi;
y = edge[l].se;
}
void build_tree(int x, int y, vector<int> &order_x, vector<int> &order_y){
queue<int> myq;
vis[x] = 1, vis[y] = 2;
myq.push(x), myq.push(y);
while (!myq.empty()){
int u = myq.front();
myq.pop();
if (vis[u] == 1)
order_x.pb(u);
else
order_y.pb(u);
for (auto v: adj[u]){
if (vis[v.fi]) continue;
vis[v.fi] = vis[u];
myq.push(v.fi);
}
}
reverse(order_x.begin(), order_x.end());
reverse(order_y.begin(), order_y.end());
}
void find_ans(vector<int> order_x, vector<int> order_y, int &x, int &y){
int l = 0, r = order_x.size()-1;
while (l < r){
int mid = (l+r)/2;
vector<int> temp(m, 0);
for (int j = 0; j <= mid; j++)
for (auto v: adj[order_x[j]])
temp[v.se] = 1;
if (ask(temp) > dis)
r = mid;
else
l = mid+1;
}
x = order_x[l];
l = 0, r = order_y.size()-1;
while (l < r){
int mid = (l+r)/2;
vector<int> temp(m, 0);
for (int j = 0; j <= mid; j++)
for (auto v: adj[order_y[j]])
temp[v.se] = 1;
if (ask(temp) > dis)
r = mid;
else
l = mid+1;
}
y = order_y[l];
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
n = N, m = U.size();
for (int i = 0; i < m; i++){
int u = U[i]+1, v = V[i]+1;
edge[i] = mp(u, v);
adj[u].pb(mp(v, i));
adj[v].pb(mp(u, i));
}
dis = ask(vector<int>(m, 0));
int x, y;
find_bridge(x, y);
//printf("bridge: x = %d, y = %d\n", x, y);
vector<int> order_x, order_y;
build_tree(x, y, order_x, order_y);
int st, en;
find_ans(order_x, order_y, st, en);
//printf("st = %d, en = %d\n", st, en);
answer(st-1, en-1);
}
/*
4 4 1 3 1 3
0 1
0 2
0 3
1 2
*/
