题目背景

这是忆哀的第多少次重生，已经无法统计。新生的花朵与离别的丧钟如同流水般流经她的眼帘。她脑中的仿佛不是过去的记忆，而也是无法改变的未来。

与其说这无穷轮回的折磨是一种「永生」，倒不如赐给她死亡。

但是这一次，她重新感受到了未知的那一丝"可能性"。跨过绝望……

在无数次重启中没有被复原的，不只是忆哀的记忆，还有那株由希望与血泪融汇，浇注生长出的来自「彼岸」的蔷薇。这便是能够与「祂」为之一战的武器。

题目描述

这株蔷薇一共生长出了 $n$ 朵花，它们之间连接形成一个树形结构。而已知有 $m$ 条路径，一条路径 $(a, b)$ 的含义是，将这条路径上的所有花朵放在一起，可以生成一种对抗神明的力量。但是一旦这种力量被生成出来，这朵花也被消耗，不能用于其他方案。也就是说，可以从树上选取一个点不相交的路径集合，每条路径得以生成一份力量。忆哀已经计算出了最多可以用这些花朵收集出多少份力量，但是……就差那么一点。

只要再多一份力量，就可以对抗神明了。

忆哀拿出剑，在手臂上划出一道伤口。她要选取一条路径，将这条路径上的花朵用鲜血染红，从而远古魔法将会得以生效，这些花朵也能够用于生成一份新的力量。

忆哀想知道，她一共有多少种不同的路径 $(x, y)$ 可以选择，也就是说将这条路径与原始的 $m$ 条路径一同考虑，能够选出来的最大的点不相交的路径集合，所包含的路径数比原来 $m$ 条路径中能选出来的路径数大。

向永恒开战，追寻我——

一如此刻，十指紧握。

将太阳射落，献给我——

请记得，我即神佛。

输入格式

第一行两个整数 $n, m$，表示蔷薇花的数量和原始的生成力量的方案数量。

接下来 $n - 1$ 行每行两个正整数 $u, v$，表示 $u$ 和 $v$ 两朵花直接相连。

接下来 $m$ 行每行两个正整数 $a, b$，表示 $a$ 到 $b$ 路径上的花朵整体可以生成一份力量。

输出格式

输出一行一个整数，表示忆哀可行的选择 $(a, b)$ 的方案数。

样例输入

8 6
1 2
1 3
1 4
1 5
5 6
5 7
7 8
2 3
2 4
3 4
1 6
5 6
5 8

样例输出

8

样例解释

原本可以选出 $2$ 条路径，例如：$(2, 3), (5, 8)$。

可以加入如下路径：

• 加入 $(2,2)$，可以选择 $3$ 条路径：$(2, 2), (3, 4), (5, 8)$。
• 加入 $(3, 3)$，可以选择 $3$ 条路径：$(3, 3), (2, 4), (5, 8)$。
• 加入 $(4, 4)$，可以选择 $3$ 条路径：$(4, 4), (2, 3), (5, 8)$。
• 加入 $(6, 6)$，可以选择 $3$ 条路径：$(6, 6), (2, 3), (5, 8)$。
• 加入 $(7, 7)$，可以选择 $3$ 条路径：$(7, 7), (2, 3), (5, 6)$。
• 加入 $(7, 8)$，可以选择 $3$ 条路径：$(7, 8), (2, 3), (5, 6)$。
• 加入 $(8, 7)$，可以选择 $3$ 条路径：$(8, 7), (2, 3), (5, 6)$。
• 加入 $(8, 8)$，可以选择 $3$ 条路径：$(8, 8), (2, 3), (5, 6)$。

因此总共有 $8$ 种加入路径的方案。

数据范围与约定

对于 $100\%$ 的数据，保证 $2\le n \le 3 \times 10^5, 0\le m \le 3\times 10^5, 1\le u, v, a, b\le n$。

数据类型的含义：

A：保证 $v = u + 1$。

B：保证 $u = 1$。

C：在树的形态上无特殊约束。

1：保证 $a = b$。

2：给出的路径无特殊约束。

时间限制：$2\texttt{s}$

空间限制：$512\texttt{MB}$

下载

样例数据下载