2530 - 运输压力

题目描述

FJ 给他的牛棚的 N 个隔间之间安装了 N-1 根管道,隔间编号从 1N。所有隔间都被管道连通了。

FJ 有 K 条运输牛奶的路线,第 i 条路线从隔间 s_i 运输到隔间 t_i。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力,你需要计算压力最大的隔间的压力是多少。

输入

第一行输入两个整数 NK

接下来 N-1 行每行输入两个整数 xy,其中 x \ne y。表示一根在牛棚 xy 之间的管道。

接下来 K 行每行两个整数 st,描述一条从 st 的运输牛奶的路线。

输出

一个整数,表示压力最大的隔间的压力是多少。

样例

输入

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

输出

9
说明

数据范围

2 \le N \le 5 \times 10^4,1 \le K \le 10^5

来源

USACO15DEC

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 0
通过人数 0
金币数量 1 枚
难度 提高


上一题 下一题