#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define sz(x) x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);
const int maxN = 5e5 + 10;
vector<int> adj[maxN];
template<typename T>
void pr(T a) {
cerr << a << endl;
}
pair<int, int> child[maxN];
pair<bool, bool> valid[maxN];
vector<int> order, low;
int curr = 0, par[maxN], pos = -1, xd = 0;
void build(int h, int node, vector<int>& x, vector<int>& y, int lg) {
if(h == lg) {
child[-node].first = curr++;
child[-node].second = curr++;
par[curr - 2] = node;
par[curr - 1] = node;
low.push_back(node);
} else {
child[-node].first = pos - 1;
child[-node].second = pos - 2;
x.push_back(child[-node].first);
y.push_back(child[-node].second);
pos -= 2;
build(h + 1, child[-node].first, x, y, lg);
build(h + 1, child[-node].second, x, y, lg);
}
}
void traverse(int node, int h, int lg) {
if(h == lg + 1) {
assert(node >= 0);
order.push_back(node);
return;
}
traverse(child[-node].first, h + 1, lg);
swap(child[-node].first, child[-node].second);
}
void create_circuit(int M, std::vector<int> A) {
int n = sz(A);
if(n == 1) {
vector<int> to(M + 1, 1), x, y;
to[0] = A[0];
to[A[0]] = 0;
answer(to, x, y);
return;
}
vector<int> to(M + 1, -1), x, y;
int logi = log2(n);
if(n == (1 << logi)) {
logi--;
}
// cout << logi << endl;
build(0, -1, x, y, logi);
for(int i = 0; i < (1 << (logi + 1)); i++) {
traverse(-1, 0, logi);
}
// cout << xd << endl;
// for(auto i: order) {
// cout << i << " ";
// } cout << endl;
int power = (1 << (logi + 1)) - n;
// cout << "pr:" << power << endl;
// cout << power << " " << (1 << logi) << endl;
for(int i = 0; i < power; i++) {
// cout << order[i] << endl;
if(!valid[-par[order[i]]].first) {
valid[-par[order[i]]].first = 1;
child[-par[order[i]]].first = -1;
} else {
valid[-par[order[i]]].second = 1;
child[-par[order[i]]].second = -1;
}
}
// cout << "done" << endl;
// cout << sz(order) << endl;
// for(auto i: order) {
// cout << i << " ";
// } cout << endl;
A.push_back(0);
int j = 1;
for(int i = power; i < (1 << (logi + 1)); i++) {
if(!valid[-par[order[i]]].first) {
valid[-par[order[i]]].first = 1;
child[-par[order[i]]].first = A[j];
} else {
valid[-par[order[i]]].second = 1;
child[-par[order[i]]].second = A[j];
}
j++;
}
for(auto i: low) {
x.push_back(child[-i].first);
y.push_back(child[-i].second);
}
to[0] = A[0];
answer(to, x, y);
// }
}
