#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
#define ll int
typedef vector <ll> vi;
typedef pair <ll,ll > ii;
typedef vector <ii> vii;
#define sz(x) (ll)x.size()
#define pb push_back
#define F first
#define S second
#define MID ((l+r)/2)
#define dbg(x) cout<<#x<<": "<<x<<endl;
#define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl;
void tabb(ll n){
for (ll i= 0; i<n; i++) cout<<"\t";
}
void printVct(vi &v){
for (ll i=0; i<sz(v); i++){
cout<<v[i]<<" ";
}
cout<<endl;
}
void printVctPair(vii &v){
for (ll i=0; i<sz(v); i++){
cout<<"("<<v[i].F<<","<<v[i].S<<") ";
}
cout<<endl;
}
void printVct2D(vector<vi> &adj){
for (ll i=0; i<sz(adj); i++){
cout<<i<<": ";
for (ll j =0; j<sz(adj[i]); j++){
cout<<"("<<adj[i][j]<<"),";
}
cout<<endl;
}
cout<<endl;
}
void printVctPair2D(vector<vii> &adj){
for (ll i=0; i<sz(adj); i++){
for (ll j =0; j<sz(adj[i]); j++){
cout<<"("<<adj[i][j].F<<","<<adj[i][j].S<<"),";
}
cout<<endl;
}
cout<<endl;
}
vector <vii> adj;
ll n,m;
long long b; //all light case value
ll solve(ll root){
queue <ll> q;
vii dis(n);
for (ll i =0; i<n; i++)
dis[i] = ii(-1, i);
dis[root].F = 0;
vi par(n, -1);
q.push(root);
while (!q.empty()){
ll u= q.front();
q.pop();
for (ll i = 0; i<sz(adj[u]); i++){
if (dis[adj[u][i].F].F == -1){
q.push(adj[u][i].F);
dis[adj[u][i].F].F = dis[u].F + 1;
par[adj[u][i].F] = adj[u][i].S;
}
}
}
sort(dis.rbegin(), dis.rend());
// cout<<"dis:";
// printVctPair(dis);
// cout<<"par:";
// printVct(par);
vi v;
ll l = 0, r = n-1, mid;
while (l < r){
mid = MID;
// dbg3(l,r,mid);
v.assign(m, 0);
// printVct(v);
for (ll i= 0; i<=mid; i++){
ll tmp = par[dis[i].S];
if (tmp != -1) v[tmp] = 1;
}
long long c =ask(v);
if (c > b){
r = mid;
}
else{
l = mid+1;
}
}
return dis[l].S;
}
void find_pair(int N, vi V, vi U, int A,int B) {
n = N; m = sz(U);
adj.assign(n, vii());
for (ll i=0; i<m ;i++){
adj[U[i]].pb(ii(V[i], i));
adj[V[i]].pb(ii(U[i], i));
}
vi v(m, 0);
b = ask(v);
ll l = 0, r = m-1, mid;
while (l < r){
mid = MID;
v.assign(m, 0);
for (ll i = 0; i<=mid; i++)
v[i] = 1;
long long c = ask(v);
if (c > b) r = mid;
else l = mid+1;
}
ll p = U[l];
// dbg(p);
ll s = solve(p);
// dbg(s);
// cout<<endl<<endl<<endl;
ll t = solve(s);
//dbg2(s,t);
answer(s, t);
}
/*
14 13 2 5 0 13
0 1
1 5
1 2
2 3
1 4
5 7
7 8
5 6
3 12
3 11
2 9
9 10
9 13
14 13 2 5 3 10
0 1
1 5
1 2
2 3
1 4
5 7
7 8
5 6
3 12
3 11
2 9
9 10
9 13
*/
