#include <bits/stdc++.h>
using namespace std;
void answer(vector<int> c, vector<int> x, vector<int> y);
namespace {
constexpr int P_MAX = 20000000;
constexpr int S_MAX = 400000;
int M, N;
std::vector<int> A;
bool answered;
int S;
std::vector<int> IC, IX, IY;
void wrong_answer(const char *MSG) {
exit(1);
}
void simulate() {
if (S > S_MAX) {
char str[50];
exit(0);
}
for (int i = 0; i <= M; ++i) {
if (!(-S <= IC[i] && IC[i] <= M)) {
wrong_answer("wrong serial number");
}
}
for (int j = 1; j <= S; ++j) {
if (!(-S <= IX[j - 1] && IX[j - 1] <= M)) {
wrong_answer("wrong serial number");
}
if (!(-S <= IY[j - 1] && IY[j - 1] <= M)) {
wrong_answer("wrong serial number");
}
}
int P = 0;
std::vector<bool> state(S + 1, false);
int pos = IC[0];
int k = 0;
for (;;) {
if (pos < 0) {
if (++P > P_MAX) {
char str[50];
exit(0);
}
state[-pos] = !state[-pos];
pos = state[-pos] ? IX[-(1 + pos)] : IY[-(1 + pos)];
} else {
if (pos == 0) {
break;
}
if (k >= N) {
wrong_answer("wrong motion");
}
if (pos != A[k++]) {
wrong_answer("wrong motion");
}
pos = IC[pos];
}
}
if (k != N) {
wrong_answer("wrong motion");
}
for (int j = 1; j <= S; ++j) {
if (state[j]) {
exit(0);
}
}
}
} // namespace
void _answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y) {
if (answered) {
wrong_answer("answered not exactly once");
}
answered = true;
// check if input format is correct
if ((int)C.size() != M + 1) {
wrong_answer("wrong array length C");
}
if (X.size() != Y.size()) {
wrong_answer("wrong array length XY");
}
S = X.size();
IC = C;
IX = X;
IY = Y;
}
void create_circuit(int m, vector<int> a) {
int n = a.size();
A = a; N = n; M = m;
vector<int> c(m + 1), x, y;
vector<vector<int>> cnt(m + 1);
cnt[0].push_back(a[0]);
a.push_back(0);
for (int i = 0; i < n; i++) {
cnt[a[i]].push_back(a[i + 1]);
}
c[0] = a[0];
queue<int> s;
vector<vector<int>> to;
for (int i = 1; i <= m; i++) {
if (cnt[i].size() == 0) {
c[i] = 0;
continue;
}
if (cnt[i].size() == 1) {
c[i] = cnt[i][0];
continue;
}
int j = x.size() + 1;
c[i] = -j;
s.push(j);
x.push_back(-j);
y.push_back(-j);
to.push_back(cnt[i]);
}
while (!s.empty()) {
int j = s.front();
s.pop();
if (to[j - 1].size() == 2) {
x[j - 1] = to[j - 1][0];
y[j - 1] = to[j - 1][1];
continue;
}
vector<int> _a, _b;
for (int i = 0; i < to[j - 1].size(); i++) {
if (i & 1) _b.push_back(to[j - 1][i]);
else _a.push_back(to[j - 1][i]);
}
if (_a.size() > _b.size()) {
_b.push_back(_a.back());
_a.pop_back();
_a.push_back(-j);
}
int k = x.size() + 1;
x[j - 1] = -k;
x.push_back(-k);
y.push_back(-k);
to.push_back(_a);
s.push(k);
k++;
y[j - 1] = -k;
x.push_back(-k);
y.push_back(-k);
to.push_back(_b);
s.push(k);
}
_answer(c, x, y);
simulate();
answer(c, x, y);
}
