#include "doll.h"
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=1e5+5, Log=17, pot=(1<<Log);
vector < int > sus[maxn];
vector < int > vez;
vector < int > x, y;
int m, n;
vector < int > red;
void napravi(int bit){
int br=0;
for(int i=0; i<(1<<bit); i++){
red.push_back(br);
for(int j=bit-1; j>-1; j--){
if((1<<j)&br){
br-=(1<<j);
}
else{
br+=(1<<j);
break;
}
}
}
/* for(int i=0; i<red.size(); i++){
cout << red[i] << ' ';
}
cout << endl;*/
}
void rijesi(){
int br;
int pos=-1;
int bit;
int raz, ind;
for(int i=1; i<=m; i++){
// cout << "usao" << endl;
if(sus[i].empty()){
vez.push_back(0);
}
else if(sus[i].size()==1){
vez.push_back(sus[i][0]);
}
else{
vez.push_back(pos);
br=1;
bit=0;
while((int)sus[i].size()>br){
br*=2;
bit++;
}
red.clear();
napravi(bit);
for(int j=1; j<br/2; j++){
x.push_back(pos-j*2+1);
y.push_back(pos-j*2);
}
raz=br-sus[i].size();
ind=0;
for(int j=br/2; j<br; j++){
x.push_back(pos);
y.push_back(pos);
}
// cout << "raz " << raz << endl;
for(int j=raz; j<br; j++){
if(red[j]&1){
// cout << "y " << pos+br/2+red[j]/2 << endl;
y[pos+br/2+red[j]/2]=sus[i][ind];
ind++;
}
else{
// cout << "x " << pos+br/2+red[j]/2 << endl;
x[pos+br/2+red[j]/2]=sus[i][ind];
ind++;
}
}
pos-=br-1;
}
}
}
void create_circuit(int M, vector <int> a){
m=M;
n=a.size();
vez.push_back(a[0]);
for(int i=0; i<n-1; i++){
sus[a[i]].push_back(a[i+1]);
}
sus[a[n-1]].push_back(0);
rijesi();
/* for(int i=0; i<(int)vez.size(); i++){
cout << vez[i] << ' ';
}
cout << endl;
for(int i=0; i<(int)x.size(); i++){
cout << x[i] << ' ' << y[i] << endl;
}*/
answer(vez, x, y);
}
