Модуль: Поиск в глубину. DFS


Задача

18 /19


Число пар районов


Задача

В Сильвертауне есть N районов, пронумерованных от 1 до N, и M дорог, пронумерованных от 1 до M. Дорога i ведет из района Ai в район Bi, но вы не можете воспользоваться ею, чтобы попасть из района Bi в район Ai.
Максимус планирует прогулки по районам города. Он начинает в некотором районе, проходит по нулю или более дорог и заканчивает в некотором районе.
Сколько пар районов могут быть отправной и конечной точкой прогулки Максимуса?
Мы различаем пары с одинаковым набором районов, расположенных в разном порядке.


Формат входных данных
Первая строка содержит два целых числа N и M. Далее идет M строк, в каждой из которых записано по 2 числа: Ai и Bi.

Ограничения 
  • 2 ≤ N ≤ 2000
  • 0 ≤ M ≤ min(2000, N*(N-1)
  • 1 ≤ Ai, Bi ≤ N
  • Ai не равно Bi.
  • Пары (Ai,Bi) уникальны.
  • Все значения во входных данных целые числа.

Формат выходных данных
Выведите ответ на задачу.


Примечание
В первом тестовом примере  есть семь пар районов, которые могут быть отправной точкой и пунктом назначения  (1,1),(1,2),(1,3),(2,2),(2,3),(3,2),(3,3)
Примеры
Входные данныеВыходные данные
1 3 3
1 2
2 3
3 2
7
2 3 0
3
3 4 4
1 2
2 3
3 4
4 1
16

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Python12
Комментарий учителя