#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
#define vi vector<int>
#define ff first
#define ss second
#define ll long long int
#define pii pair<int,int>
const int N = 2e5+100, M = 5010, K = 22;
vi go[N];
void create_circuit(int m, std::vector<int> A) {
int n = A.size();
for(int i = 0; i < n; ++i){
go[A[i]].pb(i + 1 == n ? 0 : A[i + 1]);
}
vi C(m + 1);
C[0] = A[0];
int cnt = 1;
vi X, Y;
for(int i = 1; i <= m; ++i){
if(go[i].empty()){
C[i] = 1;
}else if(go[i].size() == 1){
C[i] = go[i][0];
}else{
// for(int x: go[i]) cerr << x << ' ';
// we gotta do some stuff...
int sz;
int n = go[i].size();
for(int j = 0; ; ++j){
if((1<<j) >= n){
sz = j;
break;
}
}
// cerr << sz << ' ';
// we'll build a segtree
int fr = (1<<sz) - n; // number of bad guys, first fr states will be just redirecting to the root
// sz is actually number of layers, i-th layer has (1<<(i-1)) nodes
int root = cnt++;
// cerr << i << ' ';
// cerr << fr << ' ' << sz << " crap\n";
C[i] = -root;
vector<vi> layer(sz);
layer[0].pb(root);
for(int bit = 1; bit < sz; ++bit){
for(int num = 0; num < (1<<bit); ++num){
layer[bit].pb(cnt++);
}
}
// for(int i = 0; i < sz; ++i){
// for(int x: layer[i]) cerr << x << ' ' << i << '\n';
// }
for(int bit = 0; bit + 1 < sz; ++bit){
for(int num = 0; num < layer[bit].size(); ++num){
X.pb(-layer[bit + 1][num * 2]);
Y.pb(-layer[bit + 1][num * 2 + 1]);
}
}
vector<pii> pts;
for(int num = 0; num < (1<<(sz-1)); ++num){
pts.pb({int(X.size()), 0});
pts.pb({int(Y.size()), 1});
X.pb(-1); // smth
Y.pb(-1); // something...
}
vector<pii> ord;
for(int ii = 0; ii < (1<<sz); ++ii){
vi bits;
for(int j = 0; j < sz; ++j) bits.pb(((1<<j)&ii) > 0);
reverse(all(bits));
int ordd = 0;
for(int j = 0; j < sz; ++j) ordd += bits[j] * (1<<j);
ord.pb({ordd, ii});
}
sort(all(ord));
// for(auto [x,y ]: ord) cerr << x << ' ' << y << '\n';
for(int j = 0; j < fr; ++j){
int id = ord[j].ss;
if(pts[id].ss == 0){
X[pts[id].ff] = -root;
}else{
Y[pts[id].ff] = -root;
}
}
for(int j = fr; j < (1<<sz); ++j){
int id = ord[j].ss;
if(pts[id].ss == 0){
X[pts[id].ff] = go[i][j - fr];
}else{
Y[pts[id].ff] = go[i][j - fr];
}
}
}
}
answer(C, X, Y);
}
