#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);
int64_t y(int a, int b) {
return 1ll*(a*1e9)+b;
}
vector<int> get_leaf_order(int c_sz) {
vector<int> order;
unordered_map<int64_t, int> state;
set<int> vis;
bool done = false;
auto rec = [&] (auto&& self, int l, int r) -> void {
if (l == r) {
if (vis.count(l)) {
done = true;
return;
}
vis.insert(l);
order.push_back(l);
return;
}
int m = (l + r) >> 1;
if (state[y(l, r)] == 0) {
self(self, l, m);
}
else {
self(self, m+1, r);
}
state[y(l, r)] ^= 1;
};
while (!done) {
rec(rec, 0, c_sz-1);
}
return order;
}
void create_circuit(int M, std::vector<int> A) {
vector<int> C(M+1);
vector<vector<int>> graph(M+1);
const int n = A.size();
graph[0].push_back(A[0]);
for (int i = 0; i < n-1; ++i) {
graph[A[i]].push_back(A[i+1]);
}
graph[A[n-1]].push_back(0);
int nxt_free = -1;
map<int, pair<int, int>> sw;
for (int i = 0; i <= M; ++i) {
vector<int>& conns = graph[i];
if (!conns.size()) {
C[i] = 0;
continue;
}
if (conns.size() == 1) {
C[i] = conns.front();
continue;
}
reverse(conns.begin(), conns.end());
int lg = __lg(conns.size());
int y = 1 << lg;
if (y < conns.size()) {
y <<= 1;
while (conns.size() < y) conns.push_back(nxt_free);
}
reverse(conns.begin(), conns.end());
C[i] = nxt_free--;
vector<int> leaves;
map<int, pair<int, int>> cur_tree;
auto create_switches = [&] (auto&& self, int cur, int l, int r) {
int le = r - l + 1;
if (le == 1) {
leaves.push_back(cur);
return;
}
if (le == 2) {
leaves.push_back(cur);
return;
}
int m = (r + l) >> 1;
cur_tree[cur].first = {nxt_free};
sw[cur].first = cur_tree[cur].first;
self(self, nxt_free--, l, m);
cur_tree[cur].second = {nxt_free};
sw[cur].second = cur_tree[cur].second;
self(self, nxt_free--, m+1, r);
};
create_switches(create_switches, nxt_free+1, 0, conns.size()-1);
vector<int> order = get_leaf_order(conns.size());
for (int i = 0; i < order.size(); ++i) {
int edge = conns[i];
int leaf = order[i]/2;
int sec = order[i]%2;
if (sec) {
sw[leaves[leaf]].second = edge;
}
else {
sw[leaves[leaf]].first = edge;
}
}
}
vector<int> X, Y;
for (int i = -1; i > nxt_free; --i) {
X.push_back(sw[i].first);
Y.push_back(sw[i].second);
}
answer(C, X, Y);
}
