#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;
using int64 = long long;
using ld = long double;
constexpr int kInf = 1e9 + 10;
constexpr int64 kInf64 = 1e15 + 10;
constexpr int kMod = 1e9 + 7;
vector<int> C;
vector<int> X;
vector<int> Y;
void connect(const int x, const vector<int> &next) {
const int neighbours = (int) next.size();
if (neighbours == 0) {
C[x] = x;
} else if (neighbours == 1) {
C[x] = next[0];
} else if (neighbours == 2) {
X.push_back(next[0]);
Y.push_back(next[1]);
C[x] = -1 * (int) (X.size());
} else if (neighbours == 3) {
const int s1 = -1 * ((int) X.size() + 1);
const int s2 = s1 - 1;
const int s3 = s1 - 2;
//C[x] connections
C[x] = s1;
//s1 connections
X.push_back(s2);
Y.push_back(s3);
//s2 connections
X.push_back(next[0]);
Y.push_back(s1);
//s3 connections
X.push_back(next[1]);
Y.push_back(next[2]);
} else {
const int s1 = -1 * ((int) X.size() + 1);
const int s2 = s1 - 1;
const int s3 = s1 - 2;
//C[x] connections
C[x] = s1;
//s1 connections
X.push_back(s2);
Y.push_back(s3);
//s2 connections
X.push_back(next[0]);
Y.push_back(next[2]);
//s3 connections
X.push_back(next[1]);
Y.push_back(next[3]);
}
}
void create_circuit(int m, std::vector<int> A) {
const int n = A.size();
C.resize(m + 1);
vector<vector<int>> next(m + 1);
next[0].push_back(A[0]);
for (int i = 0; i < n - 1; i++) {
next[A[i]].push_back(A[i + 1]);
}
next[A[n - 1]].push_back(0);
for (int x = 0; x <= m; x++) {
connect(x, next[x]);
}
answer(C, X, Y);
}
