Задача
В Сильвертауне есть
N районов, пронумерованных от
1 до
N, и
M дорог, пронумерованных от
1 до
M. Дорога
i ведет из района
Ai в район
Bi, но вы не можете воспользоваться ею, чтобы попасть из района
Bi в район
Ai.
Максимус планирует прогулки по районам города. Он начинает в некотором районе, проходит по нулю или более дорог и заканчивает в некотором районе.
Сколько пар районов могут быть отправной и конечной точкой прогулки Максимуса?
Мы различаем пары с одинаковым набором районов, расположенных в разном порядке.
Формат входных данных
Первая строка содержит два целых числа
N и
M. Далее идет
M строк, в каждой из которых записано по 2 числа:
Ai и
Bi.
Ограничения
2 ≤ N ≤ 20000 ≤ M ≤ min(2000, N*(N-1)1 ≤ Ai, Bi ≤ NAi не равно 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
|