#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define ll long long
#define pb push_back
#define all(x) x.begin(), x.end()
const ll inf = 1e18;
#define pi pair<int,int>
#define f first
#define s second
const int maxn=2e5;
vector<pi> adj[maxn];
pi e[maxn];
vector<int> z;
void dfs(int u, int p) {
for(auto&ed:adj[u]) {
int v=ed.f, i=ed.s;
if (v==p) continue;
e[i]={u,v};
z.pb(i);
dfs(v,u);
}
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void find(int n, vector<int>u, vector<int>v, int a, int b) {
int shift=0;
int Z=(a&1)&(b&1);
int Q=Z;
while (!((a^b)&1)) {
++shift;
a>>=1;
b>>=1;
}
int m=u.size();
vector<int> f,s;
ll x;
Z^=a&1; Z^=1;
forn(it,18) {
f.clear(), s.clear();
vector<int> ok(n);
forn(i,n) ok[i]=rng()&1;
forn(i,n) (ok[i]?f:s).pb(i);
if (min(f.size(),s.size())==0) {
--it; continue;
}
vector<int> q(m);
forn(i,m) q[i]=(ok[u[i]]==ok[v[i]])^Z;
x = ask(q);
x>>=shift;
x^=Q;
if (x&1) {
//cout<<"!!! : "<<a<<' '<<b<<'\n';
//cout<<ask(q)<<'\n';
//for(auto&x:f) cout<<x<<' '; cout<<'\n';
//for(auto&y:s) cout<<y<<' '; cout<<'\n';
break;
}
}
if (!(x&1)) exit(0);
if (f.size()>s.size());
assert(f.size());
int l=0, r=f.size()-1;
while (l<r) {
int mid=(l+r)>>1;
vector<int> ok(n);
for(auto&x:s) ok[x]=1;
forn(i,mid+1) ok[f[i]]=1;
vector<int> q(m,0);
forn(i,m) q[i]=(ok[u[i]]==ok[v[i]])^Z;
x = ask(q);
x>>=shift;
x^=Q;
if (x&1) l=mid+1;
else r=mid;
}
int st = f[r];
//cout<<"! "<<st<<'\n';
vector<vector<pi>> g(n);
forn(i,m) {
g[u[i]].pb({v[i],i});
g[v[i]].pb({u[i],i});
}
vector<int> vis(n); vis[st]=1;
queue<int> q; q.push(st);
while (q.size()) {
auto u=q.front();q.pop();
for(auto&ed:g[u]) {
int v=ed.f, i=ed.s;
if (vis[v]) continue;
vis[v]=1;
e[i]={u,v};
q.push(v);
z.pb(i);
}
}
l=0, r=n-2;
ll S=ask(vector<int>(m,1));
while (l<r) {
int mid=(l+r)>>1;
vector<int> q(m,1);
for(int i=mid+1;i<z.size();++i) q[z[i]]=0;
ll x=ask(q);
if (x==S) r=mid;
else l=mid+1;
}
answer(st,e[z[r]].s);
}
void find_pair(int n, vector<int>u, vector<int>v, int a, int b) {
int m=u.size();
if (m!=n-1) {
find(n,u,v,a,b);
return;
}
forn(i,n-1) adj[u[i]].pb({v[i],i}), adj[v[i]].pb({u[i],i});
int k=0; forn(i,n) if (adj[i].size()==1) k=i;
dfs(k,-1);
ll s = ask(vector<int>(m,1));
int l=0, r=n-2;
while (l<r) {
int m=(l+r)>>1;
vector<int> q(n-1);
forn(i,m+1) q[z[i]]=1;
ll x=ask(q);
if (x==s) r=m;
else l=m+1;
}
k = e[z[r]].s;
//k=0;
z.clear();
dfs(k,-1);
l=0, r=n-2;
while (l<r) {
int m=(l+r)>>1;
vector<int> q(n-1);
forn(i,m+1) q[z[i]]=1;
ll x=ask(q);
if (x==s) r=m;
else l=m+1;
}
answer(k,e[z[r]].s);
}
