#include "doll.h"
//Arayi
//#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <math.h>
#include <vector>
#include <cstring>
#include <ctime>
#include <set>
#include <bitset>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <ctime>
#include <climits>
#include <cassert>
#include <chrono>
#include <random>
#include <complex>
#define fr first
#define sc second
#define MP make_pair
#define ad push_back
#define PB push_back
#define fastio ios_base::sync_with_stdio(false); cin.tie(0);
#define lli long long int
#define y1 arayikhalatyan
#define j1 jigglypuff
#define ld long double
#define itn int
#define pir pair<int, int>
#define all(x) (x).begin(), (x).end()
#define str string
#define enl endl
#define en endl
#define cd complex<long double>
#define vcd vector<cd>
#define vii vector<int>
#define vlli vector<lli>
using namespace std;
const int N = 1e6 + 30;
const lli mod = 1e9 + 7;
const ld pi = acos(-1);
const int T = 238;
const ld e = 1e-13;
int n, m, i1 = 1;
vii fp[N];
vii c, x, y;
bool col[N];
void rec(int ii, int v)
{
if (!col[v])
{
col[v] = true;
if (x[v] == mod)
{
x[v] = fp[ii].back();
fp[ii].pop_back();
rec(ii, -c[ii] - 1);
}
else if (x[v] < 0) rec(ii, -x[v] - 1);
}
else
{
col[v] = false;
if (y[v] == mod)
{
y[v] = fp[ii].back();
fp[ii].pop_back();
rec(ii, -c[ii] - 1);
}
else if (y[v] < 0) rec(ii, -y[v] - 1);
}
}
void mk(int ii)
{
vii sm = fp[ii];
int n = sm.size();
int er = 0;
while ((1 << er) < n) er++;
int ss = (1 << er) - n;
c[ii] = -i1;
vii nax, nw;
nax.ad(i1);
i1++;
x.ad(mod), y.ad(mod);
for (int i = 1; i < er; i++)
{
for (int j = nax.size() - 1; j >= 0; j--)
{
nw.ad(i1);
y[nax[j] - 1] = -i1, i1++;
nw.ad(i1);
x[nax[j] - 1] = -i1, i1++;
x.ad(mod), x.ad(mod), y.ad(mod), y.ad(mod);
}
if (ss & (1 << (er - i)))
{
x[nax[0] - 1] = c[ii];
i1--;
x.pop_back();
y.pop_back();
nw.pop_back();
}
reverse(all(nw));
swap(nax, nw);
nw.clear();
}
if (ss & 1)
{
x[nax[0] - 1] = c[ii];
}
reverse(all(fp[ii]));
rec(ii, -c[ii] - 1);
}
void create_circuit(int M, vector<int> A) {
n = A.size();
m = M;
c.resize(m + 1);
c[0] = A[0];
for (int i = 0; i < n - 1; i++)
{
fp[A[i]].ad(A[i + 1]);
}
fp[A[n - 1]].ad(0);
for (int i = 1; i <= m; i++)
{
if (fp[i].size() == 0)
{
c[i] = 0;
continue;
}
bool bl = true;
for (auto p : fp[i])if (p != fp[i][0]) bl = false;
else if (bl) c[i] = fp[i].back();
else mk(i);
}
answer(c, x, y);
}
