#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
#define sz(x) (int)x.size()
// void answer(vector<int> &C, vector<int> tmp1, vector<int> tmp2)
// {
// for (auto &x : C)
// cout << x << " ";
// cout << '\n';
// for (auto x : tmp1)
// cout << x << " ";
// cout << '\n';
// for (auto x : tmp2)
// cout << x << " ";
// cout << '\n';
// }
void create_circuit(int M, vector<int> A)
{
int N = A.size();
vector<int> C(M + 1);
C[0] = A[0];
vector<int> make_switches;
set<int> seen;
vector<int> adj[M + 1];
adj[0].push_back(A[0]);
for (int i = 0; i < N; i++)
{
if (i < N - 1)
adj[A[i]].push_back(A[i + 1]);
else
adj[A[i]].push_back(0);
if (adj[A[i]].size() == 1)
C[A[i]] = adj[A[i]][0];
else if (seen.find(A[i]) == seen.end())
{
make_switches.push_back(A[i]);
seen.insert(A[i]);
}
}
int sz_switches = make_switches.size();
// for (auto x : make_switches)
// cout << x << " ";
// cout << '\n';
vector<int> X, Y;
int S = 0;
for (int i = 0; i < sz_switches; i++)
{
int root_switch = -(++S);
int trigger_id = make_switches[i];
C[trigger_id] = root_switch;
if (sz(adj[trigger_id]) == 2)
{
X.push_back(adj[trigger_id][0]);
Y.push_back(adj[trigger_id][1]);
}
else
{
int left = -(++S);
int right = -(++S);
X.push_back(left), Y.push_back(right);
if (sz(adj[trigger_id]) == 3)
{
X.push_back(adj[trigger_id][0]), Y.push_back(root_switch);
X.push_back(adj[trigger_id][1]), Y.push_back(adj[trigger_id][2]);
}
else
{
X.push_back(adj[trigger_id][0]), Y.push_back(adj[trigger_id][2]);
X.push_back(adj[trigger_id][1]), Y.push_back(adj[trigger_id][3]);
}
}
}
answer(C, X, Y);
}
// int main()
// {
// vector<int> A = {1, 2, 1, 3, 1, 4};
// int M = 4;
// create_circuit(M, A);
// return 0;
// }
