#include "doll.h"
#include<cstdio>
#include<algorithm>
#include<queue>
#define N_ 101000
using namespace std;
int n, m, Out[N_], cnt, chk[N_*10], PV;
int RR[N_ * 10][2], vv[N_*10], Num[N_*10], ReNum[N_*10];
vector<int>E[N_], TP;
void Go(int a, int L, int cur, int ed) {
if (L == 1) {
if (RR[a][cur & 1]) {
RR[RR[a][cur & 1]][0] = ed;
return;
}
RR[a][cur & 1] = ed;
return;
}
if (!RR[a][cur & 1])RR[a][cur & 1] = ++cnt;
Go(RR[a][cur & 1], L - 1, cur >> 1, ed);
}
int Make() {
int ret = cnt + 1;
int i, sz = 1, cc = 0, j;
int L = TP.size();
while (sz < L) sz *= 2, cc++;
for (i = 1; i < sz/2; i++) {
RR[cnt + i][0] = cnt + i * 2;
RR[cnt + i][1] = cnt + i * 2 + 1;
}
int ccc = 0;
for (i = 0; i < sz; i++) {
int t = 0;
for (j = 0; j < cc; j++) {
t = t * 2 + ((i >> j) & 1);
}
int nxt;
if (t < sz - L) {
nxt = ret;
}
if (t >= sz - L) {
nxt = -TP[ccc++];
}
RR[cnt + sz / 2 + (t >> 1)][t & 1] = nxt;
}
for (i = cnt + sz - 1; i >= ret; i--) {
int x = i - cnt;
if (RR[i][0] >= 0 && RR[i][1] >= 0 && RR[i][0] == ret && RR[i][1] == ret) {
RR[cnt + x / 2][x & 1] = ret;
vv[i] = 1;
}
}
cnt += sz - 1;
return -ret;
}
void create_circuit(int M, std::vector<int> A) {
n = A.size();
m = M;
E[0].push_back(A[0]);
int i;
for (i = 0; i < n - 1; i++) {
E[A[i]].push_back(A[i + 1]);
}
E[A[n - 1]].push_back(0);
for (i = 0; i <= M; i++) {
if (E[i].size() == 0) Out[i] = 0;
else if (E[i].size() == 1)Out[i] = E[i][0];
else {
TP = E[i];
Out[i] = Make();
}
}
int ct = 0;
for (i = 1; i <= cnt; i++) {
if (!vv[i]) {
Num[i] = ++ct;
ReNum[ct] = i;
}
}
vector<int>C(m+1), X(ct), Y(ct);
for (i = 0; i <= m; i++)C[i] = Out[i];
for (i = 0; i < ct; i++) {
int x = RR[ReNum[i + 1]][0];
int y = RR[ReNum[i + 1]][1];
if (x > 0)x = Num[x];
if (y > 0)y = Num[y];
x = -x, y = -y;
X[i] = x, Y[i] = y;
}
answer(C, X, Y);
}
