#include "doll.h"
#include <iostream>
#include <assert.h>
#include <algorithm>
#include <vector>
#define forn(i,n) for(int i=0;i<(int)n;++i)
#define forit(i,a,n) for(int i=a;i<=(int)n;++i)
#define DBG(a) cerr<<#a<<" = "<<(a)<<endl
#define DBGA(a) cerr<<#a<<" = "<<(a)<<", ";
#define DBG2(a,b) do{DBGA(a)DBG(b);}while(0)
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(),a.end()
using namespace std;
template<typename T>
ostream &operator<<(ostream &os, vector<T>&v){
os<<"[";
forn(i,SZ(v)){
if(i) os<<", ";
os<<v[i];
}
os<<"]";
return os;
}
const int INF = 1000000000;
struct Graph{
int n;
vector<vector<int>> g;
vector<int> e;
vector<bool> s;
Graph(int m){
resize(m);
}
void resize(int m){
n=m;
g.resize(n);
s.resize(n);
e.resize(n);
}
void add(int u, int v){
if(max(u,v)>=n) resize(max(u,v)+1);
assert(SZ(g[u])<=2);
g[u].push_back(v);
}
void complete(){
forn(i,n) while(SZ(g[i]) < 2) add(i,-1); // lo lleva a otro lado
}
int simulate(vector<int> &a){
int u = 0;
int ret = 1; // entra aqui
while(u != -1){
//~ DBG(u);
++ret;
int v = g[u][s[u]];
s[u] = !s[u];
if(v == -1){
++e[u];
assert(e[u] <= 2);
a.push_back(u);
}
u = v;
}
//~ DBG(s);
//~ LINE;
//~ DBG(ret);
return ret;
}
int simulate(int x, vector<int> &a){
int ret = 0;
forn(_,x){
ret += simulate(a);
//~ DBG2(_+1,ret);
}
forn(i,n) assert(!s[i]);
return ret;
}
};
Graph buildBT(int n){ // no tiene sentido llamarlo con n = 1
if(n == 2){
Graph g(1);
g.complete();
return g;
}
Graph g(1); // todavía no tiene un tamaño fijo
int m = (n+1)/2;
vector<int> prev(m);
int u = 0; // nodos usados
forn(i,m) prev[i] = ++u;
for(int i=m-1;i>=0;--i){
if(n>=2) n-=2;
else if(n==1) g.add(prev[i],0), --n;
else g.add(prev[i],0), g.add(prev[i],0);
}
while(SZ(prev)>2){
vector<int> curr;
while(SZ(prev)){
curr.push_back(++u);
if(SZ(prev)>=2){
forn(_,2){
g.add(u, prev.back());
prev.pop_back();
}
reverse(ALL(g.g[u]));
} else{
g.add(u,0);
g.add(u, prev.back());
prev.pop_back();
}
}
reverse(ALL(curr));
swap(curr,prev);
}
g.add(0,prev[0]);
g.add(0,prev[1]);
g.complete();
return g;
}
void create_circuit(int M, std::vector<int> A) {
int n = SZ(A);
vector<int> nxt[M+1];
A.push_back(0); // para que el ultimo se conecte
forn(i,n){
nxt[A[i]].push_back(A[i+1]);
}
int node = 0; // luego los tengo que tratar como negativos
vector<int> C(M+1), X, Y;
C[0] = A[0]; // arranca de una
forit(i,1,M){
//~ DBG(i);
if(!SZ(nxt[i])){
C[i] = i;
continue;
}
if(SZ(nxt[i]) == 1){ // solo conecta el siguiente
C[i] = nxt[i][0];
continue;
}
Graph g = buildBT(SZ(nxt[i]));
vector<int> idx(g.n); // indices reales
for(int &x: idx){
x = node++; // uso este node
X.push_back(INF); // falta conectar estos
Y.push_back(INF);
}
//~ DBG(g.g);
//~ DBG(idx);
//~ DBG2(X,Y);
forn(j,g.n){ // me fijo con que limita cada uno
//~ DBG(idx[j]);
if(SZ(g.g[j])>=1&&g.g[j][0]!=-1){
X[idx[j]] = -idx[g.g[j][0]]-1; // lo transforma a negativo
}
if(SZ(g.g[j])>=2&&g.g[j][1]!=-1){
Y[idx[j]] = -idx[g.g[j][1]]-1;
}
}
// conectar las salidas
//~ DBG2(X,Y);
vector<int> ord; // orden del subárbol
g.simulate(SZ(nxt[i]),ord); // esto me devuelve el orden
assert(SZ(ord) == SZ(nxt[i]));
forn(j,SZ(ord)){
int u = idx[ord[j]]; // switch es -u-1
if(X[u] == INF){
X[u] = nxt[i][j];
} else{
Y[u] = nxt[i][j];
}
}
// conectar el original
C[i] = -idx[0]-1; // con la raiz de su arbolito
}
answer(C, X, Y);
}
#ifdef LOCAL
#include "grader.cpp"
#endif
