#define DM 100001
#include <fstream>
#include <vector>
using namespace std;

ifstream fi ("lca.in");
ofstream fo ("lca.out");
int n, m, a, b, rmq[DM][18], nivel[DM];
vector <int> v[DM];

void dfs(int nod, int p)
{
	rmq[0][++rmq[0][0]] = nod;
	for (int i = 0; i < v[nod].size(); ++i)
        if (v[nod][i] != p)
            dfs(v[nod][i], nod, n + 1);
	/*for (auto i:v[nod])
		if (p != v[nod][i])
		{
			fo << p << ' ' << v[nod][i] << '\n';
			dfs(v[nod][i], nod);
		}*/
	rmq[0][++rmq[0][0]] = p;
}

void dfn(int nod, int p, int n)
{
	nivel[nod] = n;
	for (auto i:v[nod])
		if (v[nod][i] != p)
			dfn()
}

int main()
{
	fi >> n >> m >> a;
	for (int i = 2; i <= n; ++i)
	{	
		fi >> a;
		v[a].push_back(i);
		v[i].push_back(a);
	}
	dfs(1, 1);
	dfn(1, 1, 1);
	for (int i = 1; i <= rmq[0][0]; ++i)
		fo << rmq[0][i] << ' ';
	fo << '\n';
	for (int i = 1; i <= rmq[0][0]; ++i)
		fo << nivel[i] << ' ';
	return 0;
}