M. Пути длины два
2000 мс · 256 МБ · всё или ничего
Ориентированный граф задан списком рёбер. Посчитайте количество путей длины ровно два — то есть пар рёбер вида .
Вершины , , не обязаны быть различными, а рёбра берутся с учётом кратности.
Перебирать пары рёбер нельзя. Заметьте, что каждый такой путь однозначно задаётся своей средней вершиной и выбором входящего и исходящего ребра.
Формат ввода
Первая строка содержит числа () и ().
Далее идут строк с парами . Возможны петли и кратные рёбра.
Формат вывода
Одно число — количество путей длины два. Ответ помещается в 64-битный тип.
Примеры
ввод
3 2 1 2 2 3
вывод
1
ввод
1 1 1 1
вывод
1
Войдите, чтобы отправлять решения.