#include "doll.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define ll long long
#define all(a) (a).begin(), (a).end()
void create_circuit(int M, vector<int> A) {
int N = A.size();
A.push_back(0);
vector<int> C(M + 1);
vector<vector<int>> con(M+1);
for(ll i = 0; i < N; i++)
{
con[A[i]].emplace_back(A[i+1]);
}
int nx = -1;
vector<int> X(2*N + 10), Y(2*N + 10);
C[0] = A[0];
auto solve = [&](ll pos) -> void
{
// cout << "\nSolving " << pos << "\n";
if(con[pos].empty())
{
// cout << "No connection, going to " << 0 << "\n";
C[pos] = 0;
return;
}
if(con[pos].size() == 1)
{
// cout << "Single connection\n";
C[pos] = con[pos][0];
return;
}
// cout << con[pos].size() << " " << __builtin_popcount(con[pos].size()) << " " <<
// __bit_width((uint32_t)con[pos].size()) << "\n";
int depth = (__builtin_popcount(con[pos].size()) == 1) ?
__bit_width((uint32_t)con[pos].size())-1 :
__bit_width((uint32_t)con[pos].size());
int last = (1 << depth)-1;
// cout << "Depth: " << depth << " last: " << last << "\n";
int first_node = 0;
function<int(ll, ll)> prop = [&](ll val, ll dep) -> int
{
int node = nx;
nx--;
if(dep == 0) first_node = node;
int x,y;
if(dep == depth-1)
{
ll val1 = val;
ll val2 = val + (1 << dep);
// cout << val1 << " " << val2 << " " << con[pos].size() << "\n";
if(val1 < con[pos].size()-1)
{
x = con[pos][val1];
}
else if(val1 == last)
{
x = con[pos].back();
}
else
{
x = first_node;
}
if(val2 < con[pos].size()-1)
{
y = con[pos][val2];
}
else if(val2 == last)
{
y = con[pos].back();
}
else
{
y = first_node;
}
}
else
{
x = prop(val, dep+1);
y = prop(val + (1<<dep), dep+1);
}
// cout << "Setting " << -(node+1) << " to " << x << ", " << y << "\n";
X[-(node+1)] = x;
Y[-(node+1)] = y;
return node;
};
C[pos] = prop(0, 0);
};
for(int i = 1; i <= M; i++)
{
solve(i);
}
X.resize(-(nx+1));
Y.resize(-(nx+1));
assert(-(nx+1) == X.size() && X.size() == Y.size());
assert(C.size() == M+1);
answer(C, X, Y);
}
