#include "doll.h"
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
const ll NMAX = 200002; // el tamaño del camino
const ll MMAX = 100002; // el numero de triggers
vector<int>C, X, Y;
ll n, m, curr = -1;
struct subarbol
{
subarbol *L, *R;
int deg, nodel=-99, noder=-99, indxRoot, thisIndex;
bool first;
subarbol(int dg, int indxR){
thisIndex = curr--;
//cout<<"created at "<<indxR << " " << dg<<endl;
deg=dg;
first = true;
indxRoot=indxR;
if(dg>1){
L = new subarbol(dg-1, indxR);
R = new subarbol(dg-1, indxR);
X[-thisIndex]=L->thisIndex;
Y[-thisIndex]=R->thisIndex;
}
}
bool insert(int value, bool firsted){
//cout<<thisIndex<<" "<<deg<< " " << first << " " << firsted << " " << value << endl;
if(deg>1){
if(first){
first=!first;
return L->insert(value, true);
}else{
first=!first;
return R->insert(value, firsted);
}
}else{
if(first)firsted=true;
if(value){
if(first)nodel = value;
else {
noder = value;
}
first=!first;
X[-thisIndex]=nodel;
Y[-thisIndex]=noder;
return true;
}else{
if(!firsted){
noder = value;
first=!first;
X[-thisIndex]=nodel;
Y[-thisIndex]=noder;
return true;
}else{
if(first)nodel = indxRoot;
else noder = indxRoot;
first=!first;
X[-thisIndex]=nodel;
Y[-thisIndex]=noder;
return false;
}
}
//cout<<indxRoot << " " <<nodel << " " << noder << endl;
}
}
};
vector<int>recorrido;
vector<int>adj[MMAX];
vector<subarbol *>jungla;
bool created[MMAX];
void put(int dd, int ht){
if(!created[dd]){
C[dd]=ht;
}else{
if(ht==0){
while(!jungla[dd]->insert(ht, false)){
}
}else{
jungla[dd]->insert(ht, false);
}
//llenar el arbol de dd con ht;
}
}
void crearArbol(int nod){
ll pot = adj[nod].size(), ans = 0;
while(pot>1){
if(pot%2==1)pot++;
pot/=2;
ans++;
}
//cout<<"creando para " << nod<<endl;
C[nod]=curr;
jungla[nod] = new subarbol(ans, curr);
created[nod]=true;
}
void create_circuit(int M, std::vector<int> A) {
A.push_back(0);
n = A.size(), m=M;
C.pb(0);
for(int i = 1 ; i <= m ; i ++){
subarbol *x;
C.pb(i);
jungla.pb(x);
}
for(int i = 0 ; i < 400000 ; i++)X.pb(0), Y.pb(0);
subarbol *x;
jungla.pb(x);
for(int i = 0 ; i < n-1 ; i++){
adj[A[i]].pb(A[i+1]);
}
adj[0].pb(A[0]);
int current = 0;
for(int i = 0 ; i < n ; i++){
//tengo que ir a A[i]
//cout<<" A ";
if(adj[current].size()<=1 || created[current]){
put(current, A[i]);
}else{
crearArbol(current);
put(current, A[i]);
}
current=A[i];
}
/*
cout<<endl;
for(int i = 0 ; i <= m ; i++){
cout<<C[i]<<" ";
}
cout<<endl;
for(int i = 0 ; i < -curr ; i ++){
cout<<X[i] << " " << Y[i] << endl;
}*/
vector<int>ansX, ansY;
for(int i = 1 ; i < -curr ; i++){
ansX.pb(X[i]);
ansY.pb(Y[i]);
}
answer(C, ansX, ansY);
}
