#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
void create_circuit(int m, vector<int> a) {
int n = a.size();
vector<vector<int>> g(m + 1);
for (int i = 0; i < n; i++) {
if (i + 1 < n) {
g[a[i]].push_back(a[i + 1]);
} else {
g[a[i]].push_back(0);
}
}
vector<int> c(m + 1), x, y, xl, yl, st;
int t = 0;
auto build = [&](const auto &build, int v, int sz) -> void {
x.push_back(-1);
y.push_back(-1);
xl.push_back(0);
yl.push_back(0);
st.push_back(0);
if (sz == 2) return;
x[v] = t++;
xl[v] = -(x[v] + 1);
build(build, x[v], sz >> 1);
y[v] = t++;
yl[v] = -(y[v] + 1);
build(build, y[v], sz >> 1);
};
vector<pair<int, int>> vv;
auto insert = [&](const auto &insert, int v) -> void {
if (st[v]) {
if (y[v] != -1) {
insert(insert, y[v]);
} else {
vv.push_back({v, 1});
}
st[v] = 0;
} else {
if (x[v] != -1) {
insert(insert, x[v]);
} else {
vv.push_back({v, 0});
}
st[v] = 1;
}
};
for (int i = 1; i <= m; i++) {
if (g[i].empty()) continue;
if (g[i].size() == 1) {
c[i] = g[i][0];
} else {
c[i] = t++;
int t = g[i].size(), l = 1;
while (l < t) {
l *= 2;
}
build(build, c[i], l);
for (int j = 0; j < l; j++) {
insert(insert, c[i]);
}
c[i] = -(c[i] + 1);
for (int j = 0; j < l - t; j++) {
if (vv[j].second == 0) {
xl[vv[j].first] = c[i];
} else {
yl[vv[j].first] = c[i];
}
}
for (int j = l - t; j < l; j++) {
if (vv[j].second == 0) {
xl[vv[j].first] = g[i][j - l + t];
} else {
yl[vv[j].first] = g[i][j - l + t];
}
}
vv.clear();
}
}
c[0] = a[0];
answer(c, xl, yl);
}
