//#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
int M, N;
vector<int> A;
vector<vector<int>> nexts;
vector<int> C, X, Y;
vector<bool> state;
void push(int* pos, int val) {
while (*pos < 0) {
state[-*pos-1].flip();
pos = !state[-*pos-1] ? &X[-*pos-1] : &Y[-*pos-1];
}
int prev = *pos;
*pos = -1-(int)X.size();
state.push_back(true);
X.push_back(prev);
Y.push_back(val);
}
void create_circuit(int __M, vector<int> __A) {
M = __M;
A = __A;
N = A.size();
nexts.resize(M+1);
for (int i = 0; i < N-1; i++) {
nexts[A[i]].push_back(A[i+1]);
}
nexts[A[N-1]].push_back(0);
C.resize(M+1);
X.reserve(3*N);
Y.reserve(3*N);
C[0] = A[0];
for (int node = 1; node <= M; node++) {
if (!nexts[node].empty()) {
C[node] = nexts[node].front();
int* root = &C[node];
for (int i = 1; i < (int)nexts[node].size(); i++) {
push(root, nexts[node][i]);
}
}
}
vector<int*> todo;
for (int i = 0; i <= M; i++) {
if (C[i] < 0) {
const int missing = (1<<__lg(2*(int)nexts[i].size()-1))-(int)nexts[i].size();
if (missing > 0) {
for (int _ = 0; _ < missing; _++) {
todo.push_back(&C[i]);
}
}
}
}
if (!todo.empty()) {
for (int i = 0; i < (int)todo.size()-1; i++) {
push(todo[i], *todo[i+1]);
}
const int lastswitch = -1-(int)X.size();
for (auto& k : C) if (k == 0) { k = lastswitch; break; }
for (auto& k : X) if (k == 0) { k = lastswitch; break; }
for (auto& k : Y) if (k == 0) { k = lastswitch; break; }
X.push_back(*todo[0]);
Y.push_back(0);
push(todo.back(), lastswitch);
}
answer(C, X, Y);
}
