#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;
void build(int h, int node, vector<int>& x, vector<int>& y, int lg) {
if(h == lg - 1) {
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) {
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;
}
int maxRep = 0;
vector<int> rep(M + 1);
for(int i = 0; i < n; i++) {
rep[A[i]]++;
maxRep = max(maxRep, rep[A[i]]);
}
if(maxRep <= 1) {
vector<int> to(M + 1, 1), em;
to[0] = A[0];
for(int i = 1; i < n; i++) {
to[A[i - 1]] = A[i];
}
to[A[n - 1]] = 0;
answer(to, em, em);
} else if( maxRep <= 2) {
vector<int> to(M + 1, 1), em;
int s = -1;
vector<int> X, Y;
A.push_back(0);
n = sz(A);
for(int i = 1; i < n; i++) {
adj[A[i - 1]].push_back(A[i]);
}
to[0] = A[0];
for(int i = 1; i <= M; i++) {
if(rep[i] == 2) {
X.push_back(adj[i][0]);
Y.push_back(adj[i][1]);
to[i] = s;
s--;
} else if(sz(adj[i])) {
to[i] = adj[i][0];
}
}
answer(to, X, Y);
} else if(maxRep <= 4) {
A.push_back(0);
n = sz(A);
vector<int> to(M + 1, 1), em;
vector<int> X, Y;
for(int i = 1; i < n; i++) {
adj[A[i - 1]].push_back(A[i]);
}
to[0] = A[0];
int s = -1;
for(int i = 1; i <= M; i++) {
if(sz(adj[i]) == 4) {
to[i] = s;
X.push_back(s - 1);
Y.push_back(s - 2);
X.push_back(adj[i][0]);
Y.push_back(adj[i][2]);
X.push_back(adj[i][1]);
Y.push_back(adj[i][3]);
s -= 3;
} else if(sz(adj[i]) == 3) {
to[i] = s;
X.push_back(s - 1);
Y.push_back(s - 2);
X.push_back(s);
Y.push_back(adj[i][1]);
X.push_back(adj[i][0]);
Y.push_back(adj[i][2]);
s -= 3;
} else if(sz(adj[i]) == 2) {
to[i] = s;
// assert(adj[i][0] == adj[i][1]);
X.push_back(adj[i][0]);
Y.push_back(adj[i][1]);
s--;
} else if(sz(adj[i])) {
to[i] = adj[i][0];
}
}
// for(int i = 0; i <= M; i++) {
// cout << to[i] << " ";
// } cout << endl;
answer(to, X, Y);
} else {
/*
if(M == 1) {
vector<int> ci{1, -1}, X, Y;
for(int i = 0; i < n; i++) {
// X.push_back(1);
// Y.push_back();
}
// answer(ci, );
} else {
}*/
// int cnt = __builtin_popcount(n);
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); i++) {
traverse(-1, 0, logi);
}
// for(auto i: order) {
// cout << i << " ";
// } cout << endl;
int power = (1 << logi) - n;
// cout << "pr:" << power << 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;
}
}
A.push_back(0);
int j = 1;
for(int i = power; i < (1 << logi); 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);
}
}
