#include <stdio.h>
#include <vector>

FILE *fin, *fout;

const int NMAX = 1e5;

int n, m;

int level[NMAX + 1];
int first[NMAX + 1];

std :: vector<int> edges[NMAX + 1];
std :: vector<int> nodes;
std :: vector<std :: vector<int>> rmq;

void dfs(int source, int crt_level) {
	level[source] = crt_level;
	nodes.push_back(source);
	first[source] = nodes.size() - 1;

	for(auto node: edges[source]) {
		if(!level[node]) {
			level[node] = crt_level + 1;
			dfs(node, crt_level + 1);
			nodes.push_back(source);
		}
	}
}

static inline int min(int a, int b) {
	if(level[a] < level[b]) {
		return a;
	}
	return b;
}

static inline unsigned int LOG2(int X) {
    return (unsigned int)(8 * sizeof(int) - __builtin_clz(X) - 1);
}

void swap(int &a, int &b) {
	a ^= b;
	b ^= a;
	a ^= b;
}

void get_rmq() {
	rmq = std :: vector<std :: vector<int>>(nodes.size(), std :: vector<int>(LOG2(nodes.size()) + 2, 0));
	for(int i = 0; i < nodes.size(); i++) {
		rmq[i][0] = nodes[i];
	}

	for(int j = 1; (1 << j) <= nodes.size(); j++) {
		for(int i = 0; i + (1 << j) - 1 < nodes.size(); i++) {
			rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
		}
	}
}

int get_lca(int node1, int node2) {
	int a = first[node1], b = first[node2];
	if(a > b) {
		swap(a, b);
	}
	printf("%d %d\n", a, b);
	int len = b - a + 1, lg = LOG2(len);
	return min(rmq[a][lg], rmq[b - (1 << lg) + 1][lg]);
}

int main() {
	fin = fopen("lca.in", "r");

	fscanf(fin, "%d %d", &n, &m);
	for(int i = 2; i <= n; i++) {
		int parent;
		fscanf(fin, "%d", &parent);
		edges[parent].push_back(i);
	}

	dfs(1, 1);

	for(int i = 0; i < nodes.size(); i++) {
		printf("%d ", nodes[i]);
	}
	printf("\n");

	for(int i = 0; i < nodes.size(); i++) {
		printf("%d ", level[nodes[i]]);
	}
	printf("\n");

	get_rmq();

	fout = fopen("lca.out", "w");
	while(m--) {
		int node1, node2;
		fscanf(fin, "%d %d", &node1, &node2);
		fprintf(fout, "%d\n", get_lca(node1, node2));
	}

	fclose(fin);
	fclose(fout);
	return 0;
}