在远处的荒野中坐落着神圣之地,它可以被视为一棵树——由 $$$n$$$ 节点和 $$$n-1$$$ 边组成的连接无向图。节点编号从 $$$1$$$ 到 $$$n$$$。
有$$$m$$$旅客被它的繁荣和美丽所吸引。于是,他们踏上了这片土地的征程。第 $$$i$$$ 个旅行者将沿着从 $$$s_i$$$ 到 $$$t_i$$$ 的最短路径行进。这样做时,它们将遍历从 $$$s_i$$$ 到 $$$t_i$$$ 的最短路径中的所有边,这在树中是唯一的。
在旅途中,旅行者会结识其他人。有些甚至可能成为朋友。具体来说,当且仅当存在至少 $$$k$$$ 条边,第 $$$i$$$ 个旅行者和第 $$$j$$$ 个旅行者都会成为朋友。
你的任务是找出满足以下条件的旅行者 $$$(i, j)$$$ 对的数量:
- $$$1 \leq i < j \leq m$$$。
- 第 $$$i$$$ 个旅行者和第 $$$j$$$ 个旅行者将成为朋友。
输入
第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$2 \le n, m \le 1.5 \cdot 10^5$$$, $$$1\le k\le n$$$)。
接下来的 $$$n-1$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u,v \le n$$$),表示 $$$u$$$ 和 $$$v$$$ 之间有一条边。
接下来的$$$m$$$行中的第$$$i$$$行包含两个整数$$$s_i$$$和$$$t_i$$$ ($$$1\le s_i,t_i\le n$$$, $$$s_i \neq t_i$$$),分别表示第$$$i$$$的起点和终点旅行者。
保证给定的边形成一棵树。
输出
唯一的一行包含一个整数 - 满足给定条件的旅行者对的数量。
示例
输入 #1
8 4 1 1 7 1 2 2 5 4 6 6 3 6 2 6 8 7 8 3 8 2 6 4 1
输出 #1
4
输入 #2
10 4 2 3 10 9 3 4 9 4 6 8 2 1 7 2 1 4 5 6 7 7 1 8 7 9 2 10 3
输出 #2
1
输入 #3
13 8 3 7 6 9 11 5 6 11 3 9 7 2 12 4 3 1 2 5 8 6 13 5 10 3 1 10 4 10 11 8 11 4 9 2 5 3 5 7 3 8 10
输出 #3
14
注意
在第一个示例中,有 $$$4$$$ 对满足给定的要求:$$$(1,2)$$$、$$$(1,3)$$$、$$$(1,4)$$$、$$$(3,4)$$$。
- $$$1$$$-st 旅行者和 $$$2$$$-nd 旅行者都穿过边缘 $$$6-8$$$。
- $$$1$$$-st 旅行者和 $$$3$$$-rd 旅行者都穿过边缘 $$$2-6$$$。
- 第$$$1$$$个旅行者和第$$$4$$$个旅行者都穿过边缘$$$1-2$$$和$$$2-6$$$。
- 第 $$$3$$$ 个旅行者和第 $$$4$$$ 个旅行者都穿过边缘 $$$2-6$$$。