#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
int N, cnter = 0;
vector<int> adj[100001];
vector<int> X(400002), Y(400002);
vector<int> C(200002);
vector<int> ord;
bitset<1500000> mark;
void chk(int a, int vv, int val, int bit){
if((1 << (bit + 1)) > adj[a].size() - 1){
ord.push_back(val); ord.push_back(val | (1 << bit));
return;
}
chk(a, vv * 2, val, bit + 1);
chk(a, vv * 2 + 1, val | (1 << bit), bit + 1);
}
void rechk(int a, int vv, int val, int bit){
if((1 << (bit + 1)) > adj[a].size() - 1){
if(adj[a][val] == -1) mark[vv * 2] = 1; else mark[vv * 2] = 0;
if(adj[a][val | (1 << bit)] == -1) mark[vv * 2 + 1] = 1; else mark[vv * 2 + 1] = 0;
mark[vv] = mark[vv * 2] & mark[vv * 2 + 1];
return;
}
rechk(a, vv * 2, val, bit + 1);
rechk(a, vv * 2 + 1, val | (1 << bit), bit + 1);
mark[vv] = mark[vv * 2] & mark[vv * 2 + 1];
}
void build(int a, int vv, int cur, int pa, int val, int bit){
if((1 << (bit + 1)) > adj[a].size() - 1){
X[abs(cur)] = adj[a][val] == -1 ? pa : adj[a][val];
Y[abs(cur)] = adj[a][val | (1 << bit)] == -1 ? pa : adj[a][val | (1 << bit)];
return;
}
if(mark[vv * 2]){
X[abs(cur)] = pa;
Y[abs(cur)] = --cnter;
build(a, vv * 2 + 1, cnter, pa, val | (1 << bit), bit + 1);
}
else if(mark[vv * 2 + 1]){
X[abs(cur)] = pa;
Y[abs(cur)] = --cnter;
build(a, vv * 2, cnter, pa, val, bit + 1);
}
else{
X[abs(cur)] = --cnter;
build(a, vv * 2, cnter, pa, val, bit + 1);
Y[abs(cur)] = --cnter;
build(a, vv * 2 + 1, cnter, pa, val | (1 << bit), bit + 1);
}
}
void create_circuit(int M, vector<int> A) {
N = A.size();
for(int i = 0; i < N - 1; i++) adj[A[i]].push_back(A[i + 1]);
adj[A[N - 1]].push_back(0);
C[0] = A[0];
for(int i = 1; i <= M; i++){
if(adj[i].size() == 0) continue;
if(adj[i].size() == 1) C[i] = adj[i][0];
else{
C[i] = --cnter;
int j = 0;
for(; j <= 20; j++){
if((1 << j) >= adj[i].size()) break;
}
vector<int> tmp((1 << j), 0);
chk(i, 1, 0, 0);
for(int k = 0; k < (1 << j) - adj[i].size(); k++) tmp[ord[k]] = -1;
int idx = 0;
for(auto x : adj[i]){
while(tmp[idx] == -1) idx++;
tmp[idx] = x;
idx++;
}
adj[i] = tmp; rechk(i, 1, 0, 0);
build(i, 1, cnter, cnter, 0, 0);
ord.clear();
}
}
vector<int> CA, XA, YA;
for(int i = 1; i <= abs(cnter); i++){
XA.push_back(X[i]); YA.push_back(Y[i]);
}
for(int i = 0; i <= M; i++) CA.push_back(C[i]);
answer(CA, XA, YA);
}
