#include "highway.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define vi vector<int>
#define vl vector<long long>
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace std;
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
vector<pii> graph[90001];
vector<pii> dij_graph[90001];
bool odw[90001];
ll cost[130001];
bool is_take[130001];
int n;
vi Q;
void bfs(int v, vi& ans)
{
queue<int> q;
q.push(v);
while(!q.empty())
{
int t = q.front();
q.pop();
ans.pb(t);
forall(it,graph[t])
{
q.push(it.ff);
}
}
reverse(all(ans));
}
void dfs(int v)
{
forall(it,graph[v])
{
if(is_take[it.ff])
{
Q[it.ss] ^= 1;
continue;
}
dfs(it.ff);
}
}
void find_pair(int N, vi U, vi V, int A, int B)
{
n = N;
int m = siz(U);
vi W(m,1);
ll base_toll = ask(W);
ll tree_toll;
int l = 0;
int r = m-1;
int edge = 0;
while(l <= r)
{
int mid = (l+r)/2;
rep(i,m) W[i] = 1;
rep2(i,0,mid) W[i] = 0;
ll new_toll = ask(W);
if(new_toll != base_toll)
{
tree_toll = new_toll;
edge = mid;
r = mid-1;
}
else
{
l = mid+1;
}
}
rep2(i,0,edge)
{
W[i] = 0;
dij_graph[U[i]].pb({V[i],i});
dij_graph[V[i]].pb({U[i],i});
cost[i] = A;
}
rep2(i,edge+1,m-1)
{
W[i] = 1;
dij_graph[U[i]].pb({V[i],i});
dij_graph[V[i]].pb({U[i],i});
cost[i] = B;
}
priority_queue<pair<ll,pii>,vector<pair<ll,pii>>,greater<pair<ll,pii>>> pq;
pq.push({0,{U[edge],-1}});
pq.push({0,{V[edge],-1}});
while(!pq.empty())
{
pair<ll,pii> t = pq.top();
pq.pop();
if(odw[t.ss.ff]) continue;
odw[t.ss.ff] = 1;
if(t.ss.ss != -1)
{
if(U[t.ss.ss] == t.ss.ff) graph[V[t.ss.ss]].pb({t.ss.ff,t.ss.ss});
else graph[U[t.ss.ss]].pb({t.ss.ff,t.ss.ss});
}
forall(it,dij_graph[t.ss.ff])
{
pq.push({t.ff+cost[it.ss],{it.ff,it.ss}});
}
}
vi tree1;
vi tree2;
bfs(V[edge],tree1);
bfs(U[edge],tree2);
l = 0;
r = siz(tree1)-1;
int a;
while(l <= r)
{
int mid = (l+r)/2;
Q = W;
rep(i,m) is_take[i] = 0;
rep(i,mid+1) is_take[tree1[i]] = 1;
dfs(tree1.back());
if((mid != siz(tree1)-1 ? ask(Q) : -1) != tree_toll)
{
a = tree1[mid];
r = mid-1;
}
else
{
l = mid+1;
}
}
l = 0;
r = siz(tree2)-1;
int b;
while(l <= r)
{
int mid = (l+r)/2;
Q = W;
rep(i,m) is_take[i] = 0;
rep(i,mid+1) is_take[tree2[i]] = 1;
dfs(tree2.back());
if((mid != siz(tree2)-1 ? ask(Q) : -1) != tree_toll)
{
b = tree2[mid];
r = mid-1;
}
else
{
l = mid+1;
}
}
answer(a,b);
}
