F. Путешествия
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Где-то в дебрях, далеко-далеко находится святая земля, которая имеет форму дерева  — связного неориентированного графа, состоящего из $$$n$$$ вершин и $$$n-1$$$ ребра. Вершины пронумерованы целыми числами от $$$1$$$ до $$$n$$$.

Всего есть $$$m$$$ путешественников, привлеченных красотой и процветанием этой земли. Каждый из них отправился в путешествие по ней. $$$i$$$-й путешественник проехал вдоль кратчайшего пути из $$$s_i$$$ в $$$t_i$$$. Во время этого путешествия, он прошел через все ребра, лежащие на кратчайшем пути из $$$s_i$$$ в $$$t_i$$$, который, как известно, единственный в дереве.

Во время своих путешествий, некоторые путешественники познакомились с остальными. Некоторые из путешественников станут друзьями. Более точно, $$$i$$$-й и $$$j$$$-й путешественники станут друзьями, тогда и только тогда, когда было хотя бы $$$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$$$.

$$$i$$$-я из следующих $$$m$$$ строк содержит два целых числа $$$s_i$$$ и $$$t_i$$$ ($$$1\le s_i,t_i\le n$$$, $$$s_i \neq t_i$$$), обозначающие начальную и конечную вершины $$$i$$$-го путешественника.

Гарантируется, что данные ребра образуют дерево.

Выходные данные

Выведите одно целое число  — количество пар путешественников, удовлетворяющих описанным условиям.

Примеры
Входные данные
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
Выходные данные
4
Входные данные
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
Выходные данные
1
Входные данные
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
Выходные данные
14
Примечание

В первом тесте существует $$$4$$$ пары, удовлетворяющие описанным условиям: $$$(1,2)$$$, $$$(1,3)$$$, $$$(1,4)$$$, $$$(3,4)$$$.

  • $$$1$$$-й путешественник и $$$2$$$-й путешественник оба пройдут по ребру $$$6-8$$$.
  • $$$1$$$-й путешественник и $$$3$$$-й путешественник оба пройдут по ребру $$$2-6$$$.
  • $$$1$$$-й путешественник и $$$4$$$-й путешественник оба пройдут по ребрам $$$1-2$$$ и $$$2-6$$$.
  • $$$3$$$-й путешественник и $$$4$$$-й путешественник оба пройдут по ребру $$$2-6$$$.