#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 DBG3(a,b,c) do{DBGA(a)DBGA(b)DBG(c);}while(0)
#define LINE cerr<<"===================================="<<endl
#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 LOG=18, 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);
//~ DBG(ret);
//~ LINE;
return ret;
}
int simulate(int x, vector<int> &a){
int ret = 0;
forn(_,x){
ret += simulate(a);
//~ DBG2(_+1,ret);
}
forn(i,n-1) assert(!s[i]); // el ultimo es un señuelo
return ret;
}
};
int node = 0;
int build(int n, Graph &g){
if(n == 1){
return -1;
}
int u = node++;
int l = build(n/2, g), r = build(n/2, g);
g.add(u,l);
g.add(u,r);
return u;
}
void create_circuit(int M, std::vector<int> A) {
int n = SZ(A);
vector<int> C(M+1), X, Y;
if(n == 1){
forit(i,1,M) C[i] = i;
C[0] = A[0];
C[A[0]] = 0;
answer(C, X, Y);
return;
}
Graph g(1);
vector<int> path;
for(int i=LOG-1;i>=0;--i){
if((1<<i)>n){
path.push_back(0);
continue;
}
int u = node++;
path.push_back(u);
}
reverse(ALL(path));
for(int i=LOG-1;i>=0;--i){
if((1<<i)>n) continue; // no me sirve
int u = path[i]; // luego hay que tratarlos como negativos
//~ DBG(u);
if(n&(1<<i)){ // si está este nodo, crear el arbolito
int aux = build(1<<i, g);
g.add(u,aux);
} else{ // no está
g.add(u,0);
}
if(i) g.add(u,path[i-1]);
else{
X.resize(node,INF);
Y.resize(node,INF);
g.add(u, node++);
}
}
g.complete(); // para el señuelo
//~ DBG(g.g);
forn(i,g.n-1){
for(int &x: g.g[i]){
if(x == -1) continue;
if(x == g.n-1){
Y[i] = 0;
continue;
}
int u = i, v = -x-1;
if(X[u] == INF) X[u] = v;
else Y[u] = v;
}
}
vector<int> ord;
g.simulate(n+1, ord);
ord.pop_back();
//~ DBG2(ord, A);
assert(SZ(ord) == SZ(A));
forn(i,SZ(ord)){
if(X[ord[i]]==INF) X[ord[i]] = A[i];
else Y[ord[i]] = A[i];
}
forit(i,0,M) C[i] = -1;
//~ DBG3(C,X,Y);
answer(C, X, Y);
}
#ifdef LOCAL
#include "grader.cpp"
#endif
