#include <bits/stdc++.h>
#include "highway.h"
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
const int maxn = 9e4+5;
ll base;
int n, m;
vector< ii > adj[maxn];
int dist[maxn];
void bfs(int s)
{
for(int i = 0; i< n; i++) dist[i] = 1e9;
dist[s] = 0;
queue<int> q; q.push(s);
while(!q.empty())
{
int u = q.front(); q.pop();
for(auto kk : adj[u])
{
int v = kk.X;
if(dist[v]> dist[u]+1)
{
dist[v] = dist[u]+1;
q.push(v);
}
}
}
}
bool cmp(int a, int b)
{
return dist[a]< dist[b];
}
int F(vector<int> &vec)
{
int lo = 0, hi = n-1;
while(lo< hi)
{
int mid = (lo+hi)/2;
vector<bool> mark(n, false);
vector<int> send(m, 1);
for(int i = 0; i<= mid; i++) mark[vec[i]] = true;
for(int i = 0; i<= mid; i++)
{
int u = vec[i];
for(auto kk : adj[u])
{
int v = kk.X, id = kk.Y;
if(mark[u] && mark[v])
{
send[id] = 0;
}
}
}
ll exp = ask(send);
if(exp == base) hi = mid;
else lo = mid+1;
}
return vec[lo];
}
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++)
{
adj[U[i]].pb({V[i], i});
adj[V[i]].pb({U[i], i});
}
base = ask(vector<int>(m, 0));
vector<int> foo;
for(int i = 0; i< n; i++) foo.pb(i);
int v = F(foo);
bfs(v); sort(foo.begin(), foo.end(), cmp);
int T = F(foo);
bfs(T); sort(foo.begin(), foo.end(), cmp);
int S = F(foo);
answer(S, T);
}
