A71457. 运输压力
编程题
提高
知识点
题目描述
FJ 给他的牛棚的 N 个隔间之间安装了 N-1 根管道，隔间编号从 1 到 N。所有隔间都被管道连通了。
FJ 有 K 条运输牛奶的路线，第 i 条路线从隔间 s_i 运输到隔间 t_i。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力，你需要计算压力最大的隔间的压力是多少。
输入格式
第一行输入两个整数 N 和 K。
接下来 N-1 行每行输入两个整数 x 和 y，其中 x \ne y。表示一根在牛棚 x 和 y 之间的管道。
接下来 K 行每行两个整数 s 和 t，描述一条从 s 到 t 的运输牛奶的路线。
输出格式
一个整数，表示压力最大的隔间的压力是多少。
输入输出样例
输入 #1
5 10 3 4 1 5 4 2 5 4 5 4 5 4 3 5 4 3 4 3 1 3 3 5 5 4 1 5 3 4
输出 #1
9
说明/提示
数据范围
2 \le N \le 5 \times 10^4,1 \le K \le 10^5