Где-то в дебрях, далеко-далеко находится святая земля, которая имеет форму дерева — связного неориентированного графа, состоящего из \(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\)-й путешественники станут друзьями.
Выходные данные
Выведите одно целое число — количество пар путешественников, удовлетворяющих описанным условиям.
Примечание
В первом тесте существует \(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\).
| № | Входные данные | Выходные данные |
|
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
|
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
|
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
|
14
|