题目背景

译自 ROI 2016 Day2 T3. Курьерская служба

题目描述

在一家公司里有 $n$ 名员工，其中一人是董事。除了董事以外，每位员工都恰好有一位直属上级。

每位员工都有自己明确的工作职责。如果员工 $a$ 需要完成员工 $b$ 的工作，就必须向员工 $b$ 发送申请。根据公司制度，申请只能在员工与其直属上级之间直接传递：要么由员工传给直属上级，要么由上级传给直属下属。申请会在员工之间逐级传递，直到抵达员工 $b$。

为了减轻员工负担，公司雇佣了 $k$ 名快递员。第 $i$ 位快递员专门负责在员工 $a_i$ 与 $b_i$ 之间传递申请。当这两人中的一方需要将申请传递给另一方时，他会将申请交给快递员。快递员会按照公司制度依次传递申请，经过所有必要的中间员工，最终将其送达目标。在传递一份申请的过程中，快递员不会重复访问同一名员工。

为了优化开支，公司决定找到一对路径重合度最高的快递员，解雇其中一人，并将其工作交由另一人承担。我们定义快递员对的重合度为：这两名快递员路径中共同包含的“员工与其直属上级之间的双向通路”的数量。

请编写一个程序，找出重合度最大的两名快递员。

输入格式

第一行包含两个整数 $n$ 和 $k$，分别表示员工人数与快递员人数（$2 \le n, k \le 2 \cdot 10^5$）。员工编号为 $1$ 到 $n$，董事编号为 $1$。

第二行包含 $n-1$ 个整数：$p_2, p_3, \ldots, p_n$，表示除董事外每位员工的直属上级编号（$1 \le p_i < i$）。

接下来 $k$ 行，每行包含两个整数 $a_i$ 和 $b_i$，表示第 $i$ 位快递员负责的员工对（$1 \le a_i, b_i \le n$，且 $a_i \ne b_i$）。可能有多个快递员负责同一对员工。

输出格式

第一行输出一个整数——两名快递员的最大重合度。

第二行输出两个不同的整数，范围为 $1$ 到 $k$，表示一对重合度最大的快递员编号。如果存在多组最优答案，输出任意一组即可。

4 2
1 2 2
1 3
1 4

1
2 1

4 2
1 2 3
1 2
3 4

0
1 2

7 3
1 2 2 4 5 5
1 3
3 7
6 1

2
2 3

4 3
1 2 3
1 4
4 1
1 4

3
2 1

提示

样例解释

在第一个样例中，有两名快递员：

• 第 1 名快递员负责在员工 1 与 3 之间传递申请。例如，从 1 传给 3 的过程中，申请先从 1 到 2，再从 2 到 3。
• 第 2 名快递员负责在员工 1 与 4 之间传递申请。例如，从 4 传给 1 的过程中，申请先从 4 到 2，再从 2 到 1。

两人路径的重合度为 1，因为他们都经过了员工 1（董事）与员工 2 之间的通路。

在第二个样例中，两名快递员的路径没有交集，因此重合度为 0。

在第三个样例中（见图示）：

• 第一名快递员路径为员工 1 → 3；
• 第二名快递员路径为员工 3 → 7；
• 第三名快递员路径为员工 6 → 1。

:::align{center} :::

其中：

• 第 1 与第 2 名快递员的路径重合在边 (2,3)；
• 第 1 与第 3 名快递员的路径重合在边 (1,2)；
• 第 2 与第 3 名快递员的路径重合在边 (2,4) 与 (4,5)。

因此，第 2 与第 3 名快递员的重合度最大，为 2。

在第四个样例中，所有快递员都传递申请于董事与员工 4 之间，因此任意一对快递员的重合度均为 3。可输出任意一对。

数据范围

子任务编号	分值	$n$	$k$	附加限制	必须通过的子任务
1	29	$2 \le n \le 100$	$2 \le k \le 100$	---
2	12	$2 \le n \le 4000$	$2 \le k \le 1000$		1
3	7	$2 \le n \le 10^5$			1–2
4	8		$2 \le k \le 5000$		1–3
5	10		$2 \le k \le 50\,000$	任意员工到董事的路径长度不超过 20
6	12			每位快递员都是重要快递员
7				---	1–6
8	10	$2 \le n \le 2 \cdot 10^5$	$2 \le k \le 2 \cdot 10^5$		1–7

翻译由 ChatGPT-5 完成