#3066. 「ROI 2016 Day2」快递

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: Planet6174

题目描述

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

给一棵包含 n 个结点的树,结点分别编为 1\ldots n 号。
树上有 k 条简单路径,路径的编号分别为 1\ldots k 。给出这些路径的端点 a_i, b_i
我们把「两条路径中的公共结点数 - 1 」称作两路径的重合长度
试求:哪两条简单路径的重合长度最大,并给出最大重合长度。

输入格式

第一行: n,k
第二行: n-1 个整数 f_2\ldots f_n f_i 表示 i 号结点与 f_i 号结点相连。
接下来 k 行: k 条路径的端点。

输出格式

第一行:最大重合长度
第二行:两条边的编号,用一个空格隔开,可以以任意顺序输出。

样例

样例输入 1

4 2
1 2 2
1 3
1 4

样例输出 1

1
2 1

样例输入 2

4 2
1 2 3
1 2
3 4

样例输出 2

0
1 2

样例输入 3

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

样例输出 3

2
2 3

样例说明 3

roi16G.png

样例输入 4

4 3
1 2 3
1 4
4 1
1 4

样例输出 4

3
2 1

数据范围与提示

子任务编号 分值 2 ⩽ n ⩽ 2 ⩽ k ⩽ 附加条件
1 29 100
2 12 4000 1000
3 7 10^5
4 8 5000
5 10 50000 路径长度小于等于 20
6 12 对于任意路径,路径上其中
一点一定是另一点的祖先
7  12 
8 10 2\cdot 10^5