#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
struct sw{
int id, x, y;
};
const int MAXM = 1e5;
const int MAXN = 1e6;
bool p = true;
int n, m, s;
int h[MAXM + 1];
vector<int> x, y, a, t, c (MAXM + 1, 0);
set <int> el;
vector<vector<int>> nxt(MAXM + 1);
void xypush(int ps, int xi, int yi){
x.push_back(xi); y.push_back(yi);
s++;
}
void show(vector<int> t){
for(int i : t) cerr << i << " ";
cerr << "\n";
}
void sw2(int i){
int xi = nxt[i][0], yi = nxt[i][1];
xypush(s, xi, yi);
}
void sw3(int i){
int xi = (s + 2) * -1, yi = (s + 3) * -1;
xypush(s, xi, yi);
xi = nxt[i][0], yi = s * -1;
xypush(s, xi, yi);
xi = nxt[i][1], yi = nxt[i][2];
xypush(s, xi, yi);
}
void sw4(int i){
int xi = (s + 2) * -1, yi = (s + 3) * -1;
xypush(s, xi, yi);
xi = nxt[i][0], yi = nxt[i][2];
xypush(s, xi, yi);
xi = nxt[i][1], yi = nxt[i][3];
xypush(s, xi, yi);
}
void swsys(int i){
int j = h[i];
if(j == 2) {
t[i] = (s + 1) * -1;
// cerr << c[i] << " " << i << "\n";
sw2(i);
}
if(j == 3) {
t[i] = (s + 1) * -1;
// cerr << c[i] << "\n";
sw3(i);
}
if(j == 4) {
t[i] = (s + 1) * -1;
// cerr << c[i] << "\n";
sw4(i);
}
}
void create_circuit(int M, std::vector<int> A) {
m = M, n = A.size(); a = A;
t = vector<int> (m + 1, 0);
//Hashing
for(int i = 0; i < n; i++) {
h[a[i]]++;
el.insert(a[i]);
if(i > 0) nxt[a[i - 1]].push_back(a[i]);
if(i == n - 1) nxt[a[i]].push_back(0);
}
t[0] = a[0];
for(int i = 0; i < n - 1; i++){
if(h[a[i]] == 1) t[a[i]] = a[i + 1];
else p = false;
}
if(p) { //Subtask 1
answer(t, x, y);
return;
}
// Creating Switch contraptions
for(int i : el){
if(h[i] > 1) swsys(i);
}
// for(int i = 0; i < n - 1; i++){
//// cerr << i << " " << c[i] << "\n";
// if(c[i] != 0) t[i] = c[i];
// }
// show(t);
// for(int i = 0; i < x.size(); i++){
// cerr << x[i] << " " << (i + 1) * - 1 << " " << y[i] << "\n";
// }
answer(t, x, y);
}
