#include <bits/stdc++.h>
#ifndef ARTHUR_LOCAL
#include "doll.h"
#endif
using namespace std;
const int MAXN=100000;
int apps[MAXN];
vector<int> go_to[MAXN];
#ifdef ARTHUR_LOCAL
void answer(vector<int> V, vector<int> X, vector<int> Y)
{
for(auto v:V) cout << v << " ";
cout << endl;
for(int i=0; i<int(X.size()); i++)
{
cout << X[i] << " " << Y[i] << endl;
}
cout << endl;
}
#endif
void create_circuit(int m, vector<int> A)
{
int n = A.size();
for(int i=0; i<n-1; i++)
{
go_to[A[i]].push_back(A[i+1]);
}
go_to[A[n-1]].push_back(0);
vector<int> C={A[0]};
int switch_no=0;
vector<int> X;
vector<int> Y;
for(int i=1; i<=m; i++)
{
if(go_to[i].empty())
{
C.push_back(0);
continue;
}
if(go_to[i].size() == 1)
{
C.push_back(go_to[i][0]);
continue;
}
if(go_to[i].size() == 2)
{
switch_no++;
C.push_back(-switch_no);
X.push_back(go_to[i][0]);
Y.push_back(go_to[i][1]);
continue;
}
}
answer(C,X,Y);
}
#ifdef ARTHUR_LOCAL
int main()
{
create_circuit(1,{1});
}
#endif
