#MX160. 军队部署
军队部署
时间限制:2000ms
空间限制:1024MB
题目描述
城镇的结构可以看作一个 个节点, 条道路构成的树。
我方派出了 支军队镇守城镇,每支军队会受到两个节点编号 ,之后在以下两种方案中选择一种:
- 在 到 的简单路径经过的道路上都部署军队。
- 在除了 到 的简单路径经过的道路之外的道路上都部署军队。
我方打算诱敌深入,因此计划把有限的兵力集中在更少的道路上,因此他需要你报告一种方案,使得有军队部署的道路数量尽可能少。
输入格式
第一行两个整数 。
接下来 行,每行两个整数 代表一条道路连接了节点 。
接下来 行,每行两个整数 代表一支军队的部署方案。
输出格式
一个整数代表有军队部署的道路数量的最小值。
样例 1 输入
6 8
1 2
1 3
1 4
1 5
3 6
2 1
4 5
6 2
6 1
6 5
6 6
1 5
2 5
样例 1 输出
3
样例2,3
见下发文件。
数据规模与约定
对于 的数据,。 对于 的数据,。 对于 的数据,。 对于另外 的数据,。 对于另外 的数据, 之间有一条道路直接相连。 对于另外 的数据,树是一条链。 对于 的数据,。