#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;
vector<bool> sw(m + 1);
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);
};
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 {
y[v] = yl[v] = u;
}
} else {
st[v] = 1;
if (x[v] != -1) {
insert(insert, x[v], u);
} 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++;
build(build, c[i], c[i], g[i].size());
for (int x : g[i]) {
insert(insert, c[i], x);
}
sw[i] = 1;
}
}
c[0] = a[0];
for (int i = 1; i <= m; i++) {
if (sw[i]) c[i] = -(c[i] + 1);
}
answer(c, xl, yl);
}
