普及模拟赛 16 - E

时空限制

时间限制 $2\text{s}$，内存限制 $1024\text{MB}$。

题目描述

城镇的结构可以看作一个 $n$ 个节点，$n - 1$ 条道路构成的树。

我方派出了 $m$ 支军队镇守城镇，每支军队会受到两个节点编号 $x_i, y_i$，之后在以下两种方案中选择一种：

• 在 $x_i$ 到 $y_i$ 的简单路径经过的道路上都部署军队。
• 在除了 $x_i$ 到 $y_i$ 的简单路径经过的道路之外的道路上都部署军队。

我方打算诱敌深入，因此计划把有限的兵力集中在更少的道路上，因此他需要你报告一种方案，使得有军队部署的道路数量尽可能少。

输入格式

第一行两个整数 $n, m$。

接下来 $n - 1$ 行，每行两个整数 $u, v$ 代表一条道路连接了节点 $u, v$。

接下来 $m$ 行，每行两个整数 $x_i, y_i$ 代表一支军队的部署方案。

输出格式

一个整数代表有军队部署的道路数量的最小值。

样例输入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

见下发文件。

数据范围

对于 $12\%$ 的数据，$1 \leq n,m \leq 16$。 对于 $24\%$ 的数据，$1 \leq n,m \leq 500$。 对于 $40\%$ 的数据，$1 \leq n,m \leq 5000$。 对于另外 $12\%$ 的数据，$1 \leq m \leq 20$。 对于另外 $12\%$ 的数据，$x_i,y_i$ 之间有一条道路直接相连。 对于另外 $12\%$ 的数据，树是一条链。 对于 $100\%$ 的数据，$1 \leq n,m \leq 10^6$。