#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 rt, 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;
if (sz == 1) {
x[v] = rt;
xl[v] = -(x[v] + 1);
return;
}
x[v] = t++;
xl[v] = -(x[v] + 1);
build(build, x[v], rt, (sz + 1) / 2);
y[v] = t++;
yl[v] = -(y[v] + 1);
build(build, y[v], rt, sz / 2);
};
vector<pair<int, int>> vv;
auto insert = [&](const auto &insert, int v, int u) -> void {
if (st[v]) {
st[v] = 0;
if (y[v] != -1) {
insert(insert, y[v], u);
} else {
if (u == -1) vv.push_back({v, 1});
else y[v] = yl[v] = u;
}
} else {
st[v] = 1;
if (x[v] != -1) {
insert(insert, x[v], u);
} else {
if (u == -1) vv.push_back({v, 0});
else x[v] = xl[v] = u;
}
}
};
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 tt = g[i].size(), l = 1;
while (l < tt) {
l *= 2;
}
if (tt == 3) l = 3;
build(build, c[i], c[i], l);
for (int j = 0; j < l; j++) {
insert(insert, c[i], (l == 3 ? g[i][j] : -1));
}
c[i] = -(c[i] + 1);
if (l != 3) {
for (int j = 0; j < l - tt; j++) {
if (vv[j].second == 0) {
xl[vv[j].first] = c[i];
} else {
yl[vv[j].first] = c[i];
}
}
for (int j = l - tt; j < l; j++) {
if (vv[j].second == 0) {
xl[vv[j].first] = g[i][j - l + tt];
} else {
yl[vv[j].first] = g[i][j - l + tt];
}
}
}
vv.clear();
}
}
c[0] = a[0];
answer(c, xl, yl);
}
