#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define el '\n'
#define pb push_back
#define pii pair <ll, ll>
#define ff first
#define ss second
#define mkp make_pair
#define fr(i, l, r) for(ll (i) = l; (i) <= r; (i)++)
#define frb(i, r, l) for(ll (i) = r; (i) >= l; (i)--)
template<class T, class S>
inline bool chmax(T &a, const S &b) {
return (a < b ? a = b, 1 : 0);
}
template<class T, class S>
inline bool chmin(T &a, const S &b) {
return (a > b ? a = b, 1 : 0);
}
ll const N = 1e5 + 10;
ll const LOG = 22;
ll const inf = 1e9 + 10;
ll const INF = 1e18 + 10;
ll const mod = 1e9 + 7;
ll const mod2 = 998244353;
ll const K = 400;
vector <int> g[N], c, x, y;
ll cur = 0;
vector <pii> fll;
void gofuck(ll i, ll st, ll l, ll r, ll left) {
ll mid = (l + r) / 2;
if(mid <= left)
x[i - 1] = st;
else {
if(l < mid) {
x.pb(0);
y.pb(0);
++cur;
x[i - 1] = -cur;
gofuck(cur, st, l, mid, left);
}
else {
fll.pb({2 * (i - 1), l - 1});
}
}
if(mid + 1 < r) {
x.pb(0);
y.pb(0);
++cur;
y[i - 1] = -cur;
gofuck(cur, st, mid + 1, r, left);
}
else {
fll.pb({2 * (i - 1) + 1, mid});
}
}
bool comp(pii a, pii b) {
while(a.ss || b.ss) {
if(a.ss % 2 != b.ss % 2)
return a.ss % 2 < b.ss % 2;
a.ss /= 2; b.ss /= 2;
}
return 0;
}
void build(ll v) {
ll s = g[v].size();
if(!s) return;
if(s == 1) {
c[v] = g[v][0];
return;
}
ll val = __lg(2 * s - 1);
val = (1 << val);
ll left = val - s;
x.pb(0); y.pb(0);
++cur;
c[v] = -cur;
gofuck(cur, -cur, 1, val, left);
sort(fll.begin(), fll.end(), comp);
ll it = 0;
for(auto [u, l] : fll) {
ll id = u / 2;
if(u % 2 == 0) {
x[id] = g[v][it];
}
else {
y[id] = g[v][it];
}
it++;
}
fll.clear();
}
void create_circuit(int M, std::vector<int> A) {
c.resize(M + 1);
g[0].pb(A[0]);
fr(i, 1, A.size() - 1)
g[A[i - 1]].pb(A[i]);
g[A.back()].pb(0);
fr(v, 0, M) {
build(v);
}
answer(c, x, y);
}
