CF1336F.Journey

In the wilds far beyond lies the Land of Sacredness, which can be viewed as a tree — connected undirected graph consisting of $n$ nodes and $n-1$ edges. The nodes are numbered from $1$ to $n$.

There are $m$ travelers attracted by its prosperity and beauty. Thereupon, they set off their journey on this land. The $i$-th traveler will travel along the shortest path from $s_i$ to $t_i$. In doing so, they will go through all edges in the shortest path from $s_i$ to $t_i$, which is unique in the tree.

During their journey, the travelers will acquaint themselves with the others. Some may even become friends. To be specific, the $i$-th traveler and the $j$-th traveler will become friends if and only if there are at least $k$ edges that both the $i$-th traveler and the $j$-th traveler will go through.

Your task is to find out the number of pairs of travelers $(i, j)$ satisfying the following conditions:

• $1 \leq i \lt j \leq m$.
• the $i$-th traveler and the $j$-th traveler will become friends.

在遥远的荒野之外，存在着神圣之地，该地可被视作一棵树——一个由 $n$ 个节点和 $n-1$ 条边构成的连通无向图。节点编号为 $1$ 到 $n$。

有 $m$ 位旅行者被其繁荣与美丽所吸引，因此启程踏上这片土地的旅程。第 $i$ 位旅行者将沿从 $s_i$ 到 $t_i$ 的最短路径行进。在此过程中，他们将遍历从 $s_i$ 到 $t_i$ 的最短路径上的所有边；由于该图为树，此最短路径是唯一的。

在旅途中，旅行者们会彼此相识，其中一些人甚至会成为朋友。具体而言，当且仅当第 $i$ 位旅行者与第 $j$ 位旅行者共同经过至少 $k$ 条边时，二者将成为朋友。

你的任务是求出满足以下条件的旅行者对 $(i, j)$ 的数量：

• $1 \leq i \lt j \leq m$；
• 第 $i$ 位旅行者与第 $j$ 位旅行者将成为朋友。

The first line contains three integers $n$, $m$ and $k$ ($2 \le n, m \le 1.5 \cdot 10^5$, $1\le k\le n$).

Each of the next $n-1$ lines contains two integers $u$ and $v$ ($1 \le u,v \le n$), denoting there is an edge between $u$ and $v$.

The $i$-th line of the next $m$ lines contains two integers $s_i$ and $t_i$ ($1\le s_i,t_i\le n$, $s_i \neq t_i$), denoting the starting point and the destination of $i$-th traveler.

It is guaranteed that the given edges form a tree.

第一行包含三个整数 $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$ 位旅行者的起点和终点。

保证所给的边构成一棵树。

The only line contains a single integer — the number of pairs of travelers satisfying the given conditions.

唯一的一行包含一个整数——满足给定条件的旅行者对的数量。

In the first example there are $4$ pairs satisfying the given requirements: $(1,2)$, $(1,3)$, $(1,4)$, $(3,4)$.

• The $1$-st traveler and the $2$-nd traveler both go through the edge $6-8$.
• The $1$-st traveler and the $3$-rd traveler both go through the edge $2-6$.
• The $1$-st traveler and the $4$-th traveler both go through the edge $1-2$ and $2-6$.
• The $3$-rd traveler and the $4$-th traveler both go through the edge $2-6$.

在第一个样例中，共有 $4$ 对旅行者满足题目要求：$(1,2)$、$(1,3)$、$(1,4)$、$(3,4)$。

• 第 $1$ 位旅行者与第 $2$ 位旅行者均经过边 $6\text{-}8$。
• 第 $1$ 位旅行者与第 $3$ 位旅行者均经过边 $2\text{-}6$。
• 第 $1$ 位旅行者与第 $4$ 位旅行者均经过边 $1\text{-}2$ 和 $2\text{-}6$。
• 第 $3$ 位旅行者与第 $4$ 位旅行者均经过边 $2\text{-}6$。