EduBrick

K. Пары с равной степенью

2000 мс · 256 МБ · всё или ничего

Неориентированный граф задан списком рёбер. Посчитайте количество пар различных вершин, у которых степени совпадают.

Пара неупорядочена: вершины uu и vv считаются один раз.

Перебирать пары нельзя: их до пяти миллиардов. Достаточно сгруппировать вершины по степени.

Формат ввода

Первая строка содержит числа nn (1≤n≤1051 \le n \le 10^5) и mm (0≤m≤2⋅1050 \le m \le 2 \cdot 10^5).

Далее идут mm строк с парами вершин. Возможны петли и кратные рёбра.

Формат вывода

Одно число — количество пар. Ответ помещается в 64-битный тип.

Примеры

ввод
5 3
1 3
2 3
2 5
вывод
2
ввод
100000 0
вывод
4999950000
Войдите, чтобы отправлять решения.