#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
const int N = int(4e5) + 10;
int c[N];
int x[N], y[N];
int switches_used;
void create_circuit(int m, vector<int> a) {
a.push_back(0);
c[0] = a[0];
int n = a.size();
vector<vector<int>> v(m + 1);
for (int i = 0; i < n - 1; i++) v[a[i]].push_back(a[i + 1]);
vector<int> leaf;
for (int i = 1; i <= m; i++) {
if (v[i].size() > 1) {
copy(v[i].begin(), v[i].end(), back_inserter(leaf));
c[i] = -1;
}
else if (v[i].size() == 1) c[i] = v[i].back();
}
int total_leaves = leaf.size();
if (total_leaves) {
int lv = 0;
while (1 << lv < total_leaves) {
for (int i = 1 << lv; i < 1 << (lv + 1); i++) x[i] = - (i << 1), y[i] = - (i << 1 | 1);
lv++;
}
for (int i = 1 << (lv - 1); i < 1 << lv; i++) x[i] = y[i] = -1;
reverse(leaf.begin(), leaf.end());
for (int i = 0; i < total_leaves; i++) {
int i0 = (1 << (lv + 1)) - 1 - i;
int r = 1 << lv;
for (int j = 0; j < lv; j++) if (i0 >> j & 1) r |= 1 << (lv - 1 - j);
if (r & 1) y[r >> 1] = leaf[i];
else x[r >> 1] = leaf[i];
}
switches_used = (1 << lv) - 1;
}
answer(vector<int>(c + 0, c + m + 1), vector<int>(x + 1, x + switches_used + 1), vector<int>(y + 1, y + switches_used + 1));
}
