#include <bits/stdc++.h>
using namespace std;
void answer(vector<int> c, vector<int> x, vector<int> y);
void create_circuit(int m, vector<int> a) {
int n = a.size();
vector<int> c(m + 1), x, y;
vector<vector<int>> cnt(m + 1);
cnt[0].push_back(a[0]);
a.push_back(0);
for (int i = 0; i < n; i++) {
cnt[a[i]].push_back(a[i + 1]);
}
c[0] = a[0];
queue<int> s;
vector<vector<int>> to;
for (int i = 1; i <= m; i++) {
if (cnt[i].size() == 0) {
c[i] = 0;
continue;
}
if (cnt[i].size() == 1) {
c[i] = cnt[i][0];
continue;
}
int j = x.size() + 1;
c[i] = -j;
s.push(j);
x.push_back(-j);
y.push_back(-j);
to.push_back(cnt[i]);
}
while (!s.empty()) {
int j = s.front();
s.pop();
if (to[j - 1].size() == 2) {
x[j - 1] = to[j - 1][0];
y[j - 1] = to[j - 1][1];
continue;
}
vector<int> _a, _b;
for (int i = 0; i < to[j - 1].size(); i++) {
if (i & 1) _b.push_back(to[j - 1][i]);
else _a.push_back(to[j - 1][i]);
}
if (_a.size() > _b.size()) {
_b.push_back(_a.back());
_a.pop_back();
_a.push_back(-j);
}
int k = x.size() + 1;
x[j - 1] = -k;
x.push_back(-k);
y.push_back(-k);
to.push_back(_a);
s.push(k);
k++;
y[j - 1] = -k;
x.push_back(-k);
y.push_back(-k);
to.push_back(_b);
s.push(k);
}
answer(c, x, y);
}
