#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 buildGeneric(int n){
Graph g(1);
n -= 2;
while(n){
g.add((g.n-1)/2,g.n);
--n;
}
g.complete();
return g;
}
Graph build(int n){
if(n == 2){
Graph g(1);
g.complete();
return g;
}
int m=(n+1)/2;
Graph g(1), l = build(m), r = build(m);
g.resize(g.n+l.n+r.n); // fusiona todo
m *= 2;
// meter los de la izquierda
forn(i,l.n){
for(int &x: l.g[i]){
if(x == -1){ // hay salidas de más
if(m > n){
g.add(i+1,0);
--m;
} else{
g.add(i+1,-1);
}
} else{
g.add(i+1,x+1); // desfasaje
}
}
}
forn(i,r.n){
for(int &x: r.g[i]){
if(x == -1){
g.add(i+l.n+1,-1);
} else{
g.add(i+l.n+1,x+l.n+1);
}
}
}
//~ DBG2(m, n);
//~ assert(m == n);
g.add(0,1);
g.add(0,l.n+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 = build(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
