Processing math: 100%

Задача C. Общий предок

Автор:Жюри летних сборов 2009   Ограничение времени:4 сек
Входной файл:lca.in   Ограничение памяти:256 Мб
Выходной файл:lca.out  
Максимальный балл:100  

Условие

Дан ориентированный граф. Подсчитайте, сколько пар вершин (i,j) имеют общего предка. Общим предком вершин i и j называется такая вершину k, что и i, и j достижимы из k.

Формат входного файла

В первой строке входного файла содержатся целые числа — количество вершин и рёбер в графе. Далее следуют M строк по два числа от 1 до N. Пара чисел (a,b) означает, что из вершины a есть ребро в вершину b.

Формат выходного файла

Выведите одно целое число — количество пар.

Ограничения

1N104

0M104

Примеры тестов

Входной файл (lca.in) Выходной файл (lca.out)
1
2 1
1 2
4
2
3 2
2 1
3 1
7

0.056s 0.009s 13