#include "doll.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
using namespace std;
void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);
int switches=0;
vector<int>copii[400005];
int out[400005];
int fiu1[400005];
int fiu2[400005];
void solve(int node,int sz,vector<int>vec)
{
if(sz==2)
{
fiu1[-node]=vec[0];
fiu2[-node]=vec[1];
return;
}
int mij=(sz)/2;
vector<int>st;
vector<int>dr;
int f1=0,f2=0;
for(int i=0;i<vec.size();i++)
{
if(vec[i]<0)
{
if(st.size()<mij)
{
f1++;
st.push_back(vec[i]);
}
else
{
f2++;
dr.push_back(vec[i]);
}
}
else
{
if(dr.size()<st.size())
{
dr.push_back(vec[i]);
}
else
{
st.push_back(vec[i]);
}
}
}
if(f1!=mij)
{
switches++;
fiu1[-node]=-switches;
solve(fiu1[-node],mij,st);
}
else
{
fiu1[-node]=vec[0];
}
switches++;
fiu2[-node]=-switches;
solve(fiu2[-node],mij,dr);
}
void make(int poz)
{
if(copii[poz].size()==0)
{
out[poz]=0;
return;
}
else if(copii[poz].size()==1)
{
out[poz]=copii[poz][0];
return;
}
else
{
switches++;
out[poz]=-switches;
int adev=copii[poz].size();
reverse(copii[poz].begin(),copii[poz].end());
while(__builtin_popcount(copii[poz].size())!=1)
{
copii[poz].push_back(out[poz]);
}
int fals=copii[poz].size()-adev;
reverse(copii[poz].begin(),copii[poz].end());
solve(out[poz],copii[poz].size(),copii[poz]);
}
}
void create_circuit(int M, std::vector<int> A) {
int N = A.size();
copii[0].push_back(A[0]);
for(int i=0;i+1<N;i++)
{
copii[A[i]].push_back(A[i+1]);
}
copii[A[N-1]].push_back(0);
vector<int>C,X,Y;
for(int i=0;i<=M;i++)
{
make(i);
C.push_back(out[i]);
// cout<<i<<" "<<out[i]<<'\n';
}
for(int i=1;i<=switches;i++)
{
X.push_back(fiu1[i]);
Y.push_back(fiu2[i]);
//cout<<-i<<" x: "<<fiu1[i]<<" y: "<<fiu2[i]<<'\n';
}
answer (C,X,Y);
}
