#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
{
if(con[pos].empty())
{
C[pos] = 0;
return;
}
if(con[pos].size() == 1)
{
C[pos] = con[pos][0];
return;
}
int depth = (__builtin_popcount(con[pos].size()) == 1) ?
__bit_width((uint32_t)con[pos].size())-1 :
__bit_width((uint32_t)con[pos].size());
// cout << "DEPTH: " << depth << "\n";
int last = (1 << depth)-1;
int first_node = 0;
vector<pair<ll,pair<ll, bool>>> tm;
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);
if(tm.size() < con[pos].size())
{
// cout << "Adding two vals\n";
tm.push_back({val1, {node, 0}});
tm.push_back({val2, {node, 1}});
}
else
{
nx++;
return first_node;
}
}
else
{
x = prop(val, dep+1);
y = prop(val + (1<<dep), dep+1);
X[-(node+1)] = x;
Y[-(node+1)] = y;
}
// cout << "Returning " << node << "\n";
return node;
};
C[pos] = prop(0, 0);
sort(all(tm), greater<pair<ll, pair<ll, bool>>>());
// cout << "Solving " << pos << "\n";
// for(auto [a, b] : tm) cout << a << " " << b.first << " " << b.second << "\n";
int sz = 0;
while(sz < con[pos].size()-1)
{
auto [node, r] = tm.back().second;
tm.pop_back();
if(r)
{
Y[-(node+1)] = con[pos][sz];
}
else
{
X[-(node+1)] = con[pos][sz];
}
sz++;
}
while(tm.size() > 1)
{
auto [node, r] = tm.back().second;
tm.pop_back();
if(r)
{
Y[-(node+1)] = first_node;
}
else
{
X[-(node+1)] = first_node;
}
}
auto [node, r] = tm.back().second;
if(r)
{
Y[-(node+1)] = con[pos].back();
}
else
{
X[-(node+1)] = con[pos].back();
}
};
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);
using ld = long double;
// ld score = 0;
// ld lg = log2(N);
// if(X.size() <= lg+N) score = 100;
// else if (X.size() <= 2*N) score = 0.5 + 0.4*pow((ld)(2*N - X.size())/(ld)(N - lg), 2);
// else score = 0;
// cout << setprecision(3) << "SCORE: " << score << "\n";
answer(C, X, Y);
}
