#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define fr first
#define sc second
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
const int nmax = 90005;
const int mmax = 130005;
long long len_edges, a, b;
int N, M, goodedge;
vector<pair<int,int>>nod[nmax];
int find_lenght(int A, int B){
vector<int>w;
for(int i=0;i<M;i++) w.push_back(0);
long long lmao = ask(w);
return lmao / A;
}
int find_index(){
int l = 0, r = M - 1, ok = 0;
while(l <= r){
int mid = l + (r - l) / 2;
vector<int>w;
for(int i=0;i<mid;i++) w.push_back(0);
for(int i=mid;i<M;i++) w.push_back(1);
long long lmao = ask(w);
if(lmao > len_edges * a){
ok = mid;
l = mid + 1;
}
else{
r = mid - 1;
}
}
return ok;
}
vector<int> bfs(int vertex1, int vertex2, vector<int>U, vector<int>V){
int marked[M], marked2[M];
for(int i=0;i<M;i++) marked2[i] = 0;
queue<int>Q;
vector<int>interesting_egdes1, interesting_egdes2;
int marked_v[N], viz[N], par[N];
for(int i=0;i<N;i++){
marked_v[i] = 0;
viz[i] = 0;
par[i] = 0;
}
par[vertex1] = -1;
Q.push(vertex1);
viz[vertex1] = 1;
Q.push(vertex2);
viz[vertex2] = 1;
marked2[goodedge] = 1;
marked_v[vertex2] = 1;
while(Q.size()){
int x = Q.front();
Q.pop();
for(auto it : nod[x]){
if(!viz[it.fr]){
if(marked_v[x] == 0){
interesting_egdes1.push_back(it.sc);
}
if(marked_v[x] == 1){
interesting_egdes2.push_back(it.sc);
marked_v[it.fr] = 1;
}
marked2[it.sc] = 1;
par[it.fr] = x;
viz[it.fr] = 1;
Q.push(it.fr);
}
}
}
int ok = vertex2;
int l = 0, r = (int)interesting_egdes2.size() - 1;
reverse(all(interesting_egdes2));
while(l <= r){
int last = 0;
int mid = l + (r - l) / 2;
vector<int>w(M);
for(int i=0;i<M;i++){
if(!marked2[i]) w[i] = 1;
}
for(int i=0;i<=mid;i++){
w[interesting_egdes2[i]] = 1;
}
last = interesting_egdes2[mid];
if(par[U[last]] == V[last]){
last = U[last];
}
else{
last = V[last];
}
long long pls = ask(w);
if(pls != len_edges * a){
ok = last;
r = mid - 1;
}
else{
l = mid + 1;
}
}
vector<int>rs;
rs.push_back(ok);
ok = vertex1;
l = 0, r = (int)interesting_egdes1.size() - 1;
reverse(all(interesting_egdes1));
while(l <= r){
int last = 0;
int mid = l + (r - l) / 2;
vector<int>w(M);
for(int i=0;i<M;i++){
if(!marked2[i]) w[i] = 1;
}
for(int i=0;i<=mid;i++){
w[interesting_egdes1[i]] = 1;
}
last = interesting_egdes1[mid];
if(par[U[last]] == V[last]){
last = U[last];
}
else{
last = V[last];
}
long long pls = ask(w);
if(pls != len_edges * a){
ok = last;
r = mid - 1;
}
else{
l = mid + 1;
}
}
rs.push_back(ok);
return rs;
}
void find_pair(int n, vector<int> U, vector<int> V, int A, int B) {
M = (int)U.size();
N = n;
a = A, b = B;
for(int i=0;i<M;i++){
nod[U[i]].push_back({V[i], i});
nod[V[i]].push_back({U[i], i});
}
len_edges = find_lenght(A, B);
int indx = find_index();
goodedge = indx;
int vertex1 = U[indx];
int vertex2 = V[indx];
vector<int>ans = bfs(vertex1, vertex2, U, V);
answer(ans[0], ans[1]);
}
