0x60图论（0x63 树的直径与最近公共祖先）例题3：暗的连锁[POJ3417]

题目描述

有一棵有 $N$ 个点 $N-1$ 条原始边的树。为了增强树上节点的连通性，另外增加 $M$ 条附加边。问题：选择切断其中两条边（需要刚好是：一条原始边 + 一条附加边），让树成为不连通的两部分，求一共有多少种不同的方案。

输入格式

第一行包含两个整数 $N$ 和 $M$； 之后 $N-1$ 行，每行包括两个整数 $A$ 和 $B$，表示 $A$ 和 $B$ 之间有一条原始边； 之后 $M$ 行以同样的格式给出附加边。

输出格式

输出一个整数表示答案。

输入输出样例

输入 #1

4 1
1 2
2 3
1 4
3 4

输出 #1

3

数据范围与提示

对于 $20\\%$ 的数据，$1 \le N,M\le 100$；

对于 $100\\%$ 的数据，$1 \le N \le 10^5,1 \le M \le 2\times 10^5$。数据保证答案不超过 $2^{31}-1$。