Ферма состоит из \(N\) полей (\(1 \leq N \leq 2 \cdot 10^5\)), последовательно
пронумерованных \(1 \ldots N\), и удобно соединённых множеством из \(M\)
двунаправленных тропинок (\(1 \leq M \leq 2 \cdot 10^5\)). Будучи
"существами привычки" коровы используют одно множество из \(N-1\) тропинок
для всех своих ежедневных перемещений между полями. Они называют эти
тропинки "стандартными" тропинками. Возможно добраться от любого поля до
любого другого поля, используя только стандартные тропинки.
Беси, желая разнообразить маршрут своей утренней пробежки, хочет
включить в маршрут нестандартные тропинки, однако не слишком много.
Она определила хороший маршрут как сформированный из простого цикла,
(возвращающего в исходное поле и не использующего никакое поле более
одного раза), который содержит ровно две нестандартные тропинки.
Помогите Беси посчитать количество хороших маршрутов,
которые она может использовать.
ФОРМАТ ВВОДА (файл exercise.in):
Первая строка ввода содержит \(N\) и \(M\). Каждая из следующих \(M\) строк
содержит два целых числа \(a_i\) и \(b_i\) описывающих конечные точки
тропинки. Первые N-1 из них - стандартные тропинки.
ФОРМАТ ВЫВОДА (файл exercise.out):
Выведите общее количество различных маршрутов, которые Беси может использовать.
Два маршрута рассматриваются как одинаковые, если они используют
одно и то же множество тропинок.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 8
1 2
1 3
1 4
1 5
2 3
3 4
4 5
5 2
|
4
|