#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<pair<int, int>> adj[100100], G[100100];
vector<int> w, rans;
int n, m, a, b, P[100100], E[100100], par[100100], cnt = -1;
ll c0;
vector<int> shit, tihs, fuck, kcuf;
ll myask(vector<int> &w){
vector<int> w2(m);
for (int i=0;i<m;i++) w2[i] = w[fuck[i]];
return ask(w2);
}
int hash_val;
void init(){
mt19937 seed(1234);
shit.resize(n); tihs.resize(n);
fuck.resize(m); kcuf.resize(m);
for (int i=0;i<n;i++) shit[i] = i;
for (int i=0;i<m;i++) fuck[i] = i;
if (hash_val&1) shuffle(shit.begin(), shit.end(), seed);
if (hash_val&1) shuffle(fuck.begin(), fuck.end(), seed);
for (int i=0;i<n;i++) tihs[shit[i]] = i;
for (int i=0;i<m;i++) kcuf[fuck[i]] = i;
}
int search1(){
int l = 0, r = n-1, ans = -1;
while(l<=r){
int m = (l+r)>>1;
fill(w.begin(), w.end(), 0);
for (int i=0;i<=m;i++) for (auto &[v, j]:adj[i]) w[j] = 1;
if (myask(w)==c0) ans = m, l = m+1;
else r = m-1;
}
fill(w.begin(), w.end(), 0);
for (int i=0;i<=ans;i++) for (auto &[v, j]:adj[i]) w[j] = 1;
return ans + 1;
}
bool visited[100100];
void bfs(int s){
queue<int> q;
q.push(s);
visited[s] = 1;
while(!q.empty()){
int cur = q.front(); q.pop();
for (auto &[nxt, i]:adj[cur]) if (!w[i] && !visited[nxt]){
G[cur].emplace_back(nxt, i);
G[nxt].emplace_back(cur, i);
visited[nxt] = 1;
w[i] = -1;
q.push(nxt);
}
}
}
void dfs(int s, int pa = -1, int idx = -1, int val = 0){
P[++cnt] = s;
E[cnt] = idx;
par[cnt] = val;
int tmp = cnt;
for (auto &[v, i]:G[s]) if (v!=pa){
dfs(v, s, i, tmp);
}
}
int search2(int mx){
int l = 1, r = mx, ans = mx+1;
while(l<=r){
int m = (l+r)>>1;
for (int i=1;i<=cnt;i++) w[E[i]] = 0;
for (int i=m;i<=mx;i++) w[E[i]] = 1;
if (myask(w)==c0) ans = m, r = m-1;
else l = m+1;
}
rans.push_back(P[--ans]);
if (ans==0) return 0;
for(;par[ans];ans=par[ans]);
//printf("ret: %d\n", ans);
return ans;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
n = N, a = A, b = B, m = U.size();
if (U.size()>=1542) hash_val = U[1542];
else hash_val = 0;
init();
for (int i=0;i<m;i++){
U[i] = shit[U[i]], V[i] = shit[V[i]];
adj[U[i]].emplace_back(V[i], fuck[i]);
adj[V[i]].emplace_back(U[i], fuck[i]);
}
w.resize(m);
c0 = myask(w);
int x = search1();
bfs(x);
for (int i=0;i<m;i++){
if (w[i]==-1) w[i] = 0;
else w[i] = 1;
}
dfs(x);
/*printf("x: %d\n", x);
printf("E: ");
for (int i=0;i<=cnt;i++) printf("%d ", E[i]);
printf("\nP: ");
for (int i=0;i<=cnt;i++) printf("%d ", P[i]);
printf("\npar: ");
for (int i=0;i<=cnt;i++) printf("%d ", par[i]);
printf("\n");*/
search2(search2(cnt)-1);
answer(tihs[rans[0]], tihs[rans[1]]);
}
