题目描述

你最近成为了一所大学的校长，并决定开设一个新的项目：训练学生进行竞技编程。因此，学生会有两类课程：体育课和编程课。

这个项目最大的特色是学生将在两个校区同时学习：偶数日去第一个校区，奇数日去第二个校区。

两个校区的结构都非常特别：每个校区都有 $n$ 间教室，编号为 $1$ 到 $n$，并且有 $n-1$ 条通道。任意两间教室之间都可以通过通道相互到达。因此，每个校区的教室和通道都构成一棵树。

不过，你发现学生很难同时记住两个校区的结构，于是决定简化他们的生活。你要选择两个不同的教室编号 $u$ 和 $v$：编号为 $u$ 的教室用于体育课，编号为 $v$ 的教室用于编程课。注意，$u$ 和 $v$ 对两个校区都相同。

你希望学生在两个校区中移动的总距离尽可能小。形式化地说，你需要找到 $u,v$，使得：

$$d_1(u,v)+d_2(u,v)$$

最小。其中 $d_1(u,v)$ 是第一个校区中教室 $u$ 到 $v$ 的距离，$d_2(u,v)$ 是第二个校区中教室 $u$ 到 $v$ 的距离。距离定义为从一个教室走到另一个教室所需经过的最少通道数。

两个校区都有入口，并且入口通向编号为 $1$ 的教室。对于其他每个教室，都有一份疏散计划：

• 在第一个校区中，$p_i$ 表示从第 $i$ 间教室走向第 $1$ 间教室的路径上的下一间教室编号；
• 在第二个校区中，$q_i$ 表示从第 $i$ 间教室走向第 $1$ 间教室的路径上的下一间教室编号。

输入格式

第一行输入一个整数 $n$，表示教室数量。

第二行输入 $n-1$ 个整数：

$$p_2,p_3,p_4,\\ldots,p_n,$$

其中 $p_i$ 表示第一个校区中，从第 $i$ 间教室到第 $1$ 间教室路径上的下一间教室。

第三行输入 $n-1$ 个整数：

$$q_2,q_3,q_4,\\ldots,q_n,$$

其中 $q_i$ 表示第二个校区中，从第 $i$ 间教室到第 $1$ 间教室路径上的下一间教室。

输出格式

第一行输出最小值：

$$d_1(u,v)+d_2(u,v).$$

第二行输出任意一对满足最小值的不同顶点 $u,v$。

数据范围

对于所有测试数据：

$$2 \le n \le 10^6,$$ $$1 \le p_i \le n,$$ $$1 \le q_i \le n.$$

输入保证两组父亲关系分别构成以 $1$ 为根的树。

样例 1

输入

5
3 1 2 3
5 4 1 3

输出

2
5 3

样例 2

输入

5
5 1 2 3
4 4 1 4

输出

2
2 4

样例 3

输入

7
1 2 2 7 1 3
5 5 5 1 5 2

输出

3
2 1

样例 4

输入

9
5 2 1 4 9 8 3 7
1 4 7 9 8 2 5 3

输出

4
2 1

样例解释

在第一个样例中，第一个校区有通道 $(3,2),(1,3),(2,4),(3,5)$；第二个校区有通道 $(5,2),(4,3),(1,4),(3,5)$。

评分方式

测试点分为 12 组。只有通过某一组的全部测试，并通过该组依赖的必要组，才能获得该组分数。注意，部分测试组不要求通过样例组。Offline 检查表示该组结果只会在比赛结束后公布。

组别	分数	附加限制	必要组	说明
0		无		样例测试
1	12	$n \le 500$	0
2	11	$n \le 5000$	0, 1
3	8	$n \le 50000$	0, 1, 2
4	11	$n \le 100000$	无	第一个校区中存在一个教室与所有其他教室直接相连
5	12			两个校区中，每个教室的相邻通道数均不超过 2
6	10		5	第一个校区中，每个教室的相邻通道数均不超过 2
7	9		0–6
8	10	$n \le 200000$	0–7
9	11	$n \le 300000$	0–8	Offline 检查
10	3	$n \le 500000$	0–9
11	2	$n \le 750000$	0–10
12	1	无	0–11