#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<pair<int, int>> adj[90002];
vector<int> w;
int now, M;
int bfsorder[90002];
bool visited[90002];
int A = -1, S = -1, T = -1;
void bfs(int x, int N)
{
for(int i=0;i<N;i++) visited[i] = false;
visited[x] = true;
queue<int> q;
q.push(x);
while(!q.empty())
{
int curr = q.front();
q.pop();
bfsorder[--now] = curr;
for(auto u : adj[curr])
{
int i = u.first, j = u.second;
if(!visited[i])
{
visited[i] = true;
q.push(i);
}
}
}
}
void makezero()
{
for(int i=0;i<M;i++) w[i] = 0;
}
void binarysearch(int l, int r, ll zerotoll)
{
if(l == r)
{
if(A == -1) A = bfsorder[l];
else if(S == -1) S = bfsorder[l];
else T = bfsorder[l];
return;
}
int mid = (l + r)/2;
makezero();
for(int i=0;i<=mid;i++)
{
for(auto u : adj[bfsorder[i]])
{
w[u.second] = 1;
}
}
ll toll = ask(w);
if(toll > zerotoll) binarysearch(l, mid, zerotoll);
else binarysearch(mid+1, r, zerotoll);
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
M = U.size();
for(int j=0;j<M;j++) { adj[U[j]].push_back({V[j], j}); adj[V[j]].push_back({U[j], j}); }
now = N; bfs(0, N);
w.resize(M);
makezero();
ll zerotoll = ask(w);
binarysearch(0, N-1, zerotoll);
now = N; bfs(A, N);
binarysearch(0, N-2, zerotoll);
now = N; bfs(S, N);
binarysearch(0, N-2, zerotoll);
answer(S, T);
}
