#include "bits/stdc++.h"
/* #include "doll.h" */
using namespace std;
using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;
#define sz(v) ((int)v.size())
#define pb push_back
#define endl '\n'
#define fst first
#define scn second
const int N = 2e5;
const int M = 2e5;
vector<int> etrig[M+2];
vector<int> ansX;
vector<int> ansY;
const ll P = 2e7;
const ll S = 4e5;
ll p = 0;
int
addindex()
{
ansX.pb(0);
ansY.pb(0);
return sz(ansX);
}
int
dfs(int x, ll s, int k)
{
assert(s<sz(etrig[x]));
/* int size = 1 + (sz(etrig[x])-s-1)/(1<<k); */
if (s+(1l<<k)>=sz(etrig[x])) return etrig[x][s];
/* if (size&1) */
/* assert(0); */
int _x = dfs(x,s,k+1);
int _y = dfs(x,s+(1<<k),k+1);
if (_x == _y)
return _x;
/* p += size; */
int indx = addindex();
assert(indx-1<sz(ansX));
assert(indx-1<sz(ansY));
ansY[indx-1] = _y;
ansX[indx-1] = _x;
return -indx;
}
int
donode(int x)
{
if (sz(etrig[x]) == 1)
return etrig[x][0];
int scount = addindex();
int last = 31 - __builtin_clz(sz(etrig[x]));
assert(last != 0);
last = (1<<last);
if (sz(etrig[x]) != last) {
last <<= 1;
int temp = etrig[x][sz(etrig[x])-1];
etrig[x][sz(etrig[x])-1] = -scount;
while (sz(etrig[x]) < last)
etrig[x].pb(-scount);
assert(last-1 < sz(etrig[x]));
etrig[x][last-1] = temp;
}
p += (1<<last);
assert(scount-1<sz(ansX));
assert(scount-1<sz(ansY));
ansX[scount-1] = dfs(x,0,1);
ansY[scount-1] = dfs(x,1,1);
return -scount;
}
void answer(vector<int> c, vector<int> X, vector<int> Y);
void
create_circuit(int m, vector<int> a)
{
int n = sz(a);
vector<int> trigexit(m+1,0);
ansX.clear();
ansY.clear();
for (int i = 0; i <= m; ++i)
etrig[i].clear();
assert(m<M+2);
for (int i = 0; i < n-1; ++i) {
assert(a[i]<M+2);
etrig[a[i]].pb(a[i+1]);
/* assert(a[i] != 0); */
}
/* assert(a[n-1] != 0); */
assert(n-1<sz(a));
assert(a[n-1]<M+2);
etrig[a[n-1]].pb(0);
trigexit[0] = a[0];
for (int i = 1; i <= m; ++i) {
assert(i < sz(trigexit));
if (sz(etrig[i]) == 0) {
trigexit[i] = 0;
} else {
trigexit[i] = donode(i);
}
}
/* if (cnt > S) { */
/* cout << "S: " << cnt << endl; */
/* } */
/* assert(cnt <= S); */
/* if (p > P) { */
/* cout << "P: " << p << endl; */
/* } */
/* assert(p <= P); */
answer(trigexit,ansX,ansY);
return;
}
#ifdef ONPC
void
answer(vector<int> c, vector<int> X, vector<int> Y)
{
vector<bool> state(sz(X));
vector<int> ans;
/* for (int i = 0; i < sz(c); ++i) { */
/* cout << i << ": " << c[i] << endl; */
/* } */
/* for (int i = 0; i < sz(X); ++i) { */
/* cout << i+1 << ": " << X[i] << ' ' << Y[i] << endl; */
/* } */
int trg = c[0];
do {
if (trg >= 0) {
ans.pb(trg);
trg = c[trg];
} else {
int indx = abs(trg)-1;
if (!state[indx]) trg = X[indx];
else trg = Y[indx];
state[indx] = !state[indx];
}
} while (trg != 0);
for (int i = 0; i < sz(X); ++i) {
if (state[i]) {
cout << 10 << endl;
/* cout << "0\n"; */
return;
}
}
for (int i = 0; i < sz(ans); ++i) {
cout << ans[i] << ' ';
}
cout << endl;
}
void
solve()
{
int m,n;
cin >> m >> n;
vector<int> c(n);
for (int i = 0; i < n; ++i) {
cin >> c[i];
}
cout << m << ' ' << n << endl;
/* vector<int> c = {1,2,1}; */
create_circuit(m,c);
}
int32_t
main()
{
/* freopen("in", "r", stdin); */
int t = 1;
/* cin >> t; */
while(t--)
solve();
}
#endif
