Маршруты для зарядки
Корова Бесси понимает, что ей нужно больше тренироваться, чтобы оставаться в хорошей форме. Ей нужна Ваша помощь в выборе возможных маршрутов по ферме, которые она может использовать для утренней пробежки.
Ферма состоит из n полей, пронумерованных от 1 до n, соединенных m двунаправленными тропами. Обладая привычкой, коровы, как правило, используют одно подмножество из n - 1 троп для своего ежедневного передвижения между полями - они называют их "стандартными" тропами. Можно путешествовать с любого поля на любое другое, используя только стандартные тропы.
Чтобы утренняя пробежка была интересной, Бесси решает выбрать маршрут с нестандартными тропами. Однако ей так комфортно пользоваться стандартными тропами, что она не хочет использовать слишком много нестандартных троп на своем маршруте. Поразмыслив, она решает, что хороший маршрут - это тот, который образует простой цикл (возвращающийся к начальной точке и не использующий какое-либо поле более одного раза), который содержит ровно две нестандартные тропы.
Помогите Бесси подсчитать количество хороших маршрутов, которые она может использовать. Два маршрута считаются одинаковыми, если они состоят из одного и того же набора троп.
Входные данные
Первая строка содержит числа n (1 ≤ n ≤ 2 * 10^5) и m (1 ≤ m ≤ 2 * 10^5). Каждая из следующих m строк содержит два целых числа a[i] и b[i] - конечные точки тропы. Первые n - 1 из них - стандартные тропы.
Выходные данные
Выведите общее количество маршрутов, которые Бесси может использовать.