#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
#define ff first
#define ss second
#define pi pair<int, int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vll vector<long long>
#define vpi vector<pair<int,int>>
#define vpll vector<pair<long long, long long>>
#define pb push_back
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)(x).size()
#define forall(it,x) for(auto& it:(x))
#define mp make_pair
pi operator+(pi a, pi b) { return mp(a.ff+b.ff, a.ss+b.ss); }
pi operator-(pi a, pi b) { return mp(a.ff-b.ff, a.ss-b.ss); }
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "circuit.h"
vector<int> ors, par(100'010, -1), is_or(100'010), where(100'010, 0);
std::string solve(int N, int R, std::vector<int> U, std::vector<int> V) {
auto Query = [&](string s) {
vector<int> x(2*N + 1);
for(int i=0; i<N; ++i) if(is_or[i]) {
x[i]^=1;
x[U[i]] ^= 1;
x[V[i]] ^= 1;
}
for(int i=0; i<2*N+1; ++i) {
if(x[i]) {
if(s[i]=='1') s[i]='0';
else s[i]='1';
}
}
return query(s);
};
vector<int> S(2*N + 1,1);
for(int i=N-1; i>=0; --i) {
int u = U[i];
int v = V[i];
S[i] = S[u] + S[v] + 1;
if(S[v] > S[u]) swap(U[i], V[i]);
}
vector<int> D(2*N + 1, 0);
for(int i=0; i<N; ++i) {
int u = U[i];
int v = V[i];
par[u] = par[v] = i;
where[v] = 1;
D[u] = D[i];
D[v] = D[i] + 1;
}
vector<vector<int>> paths;
for(int i=0; i<N; ++i) {
if(paths.size() <= D[i]) paths.pb({});
paths[D[i]].pb(i);
}
for(auto P : paths) {
int n = P.size();
auto check = [&](int mid) {
mid = min(mid, n-1);
string Q(2*N + 1, '0');
for(int i=0; i<=mid; ++i) Q[V[P[i]]] = '1';
return Query(Q);
};
int W = 64;
for(int i=0; i<n; i+=W) {
while(1) {
int lo = i;
int hi = min(n-1, i+W-1);
if(!check(hi)) break;
while(lo < hi) {
int mid = (lo+hi)/2;
if(check(mid)) hi = mid;
else lo = mid + 1;
}
ors.pb(P[lo]);
is_or[P[lo]] = 1;
}
}
for(auto x : P) is_or[x] ^= 1;
}
string res = "";
for(int i=0; i<N; ++i) res.pb('&');
for(auto x : ors) res[x] = '|';
// cerr << res << "\n";
return res;
}
