Автор: | Жюри летних сборов 2009 | Ограничение времени: | 4 сек | |
Входной файл: | lca.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | lca.out | |||
Максимальный балл: | 100 |
Дан ориентированный граф. Подсчитайте, сколько пар вершин (i,j) имеют общего предка. Общим предком вершин i и j называется такая вершину k, что и i, и j достижимы из k.
В первой строке входного файла содержатся целые числа — количество вершин и рёбер в графе. Далее следуют M строк по два числа от 1 до N. Пара чисел (a,b) означает, что из вершины a есть ребро в вершину b.
Выведите одно целое число — количество пар.
1≤N≤104
0≤M≤104
№ | Входной файл (lca.in ) |
Выходной файл (lca.out ) |
---|---|---|
1 |
|
|
2 |
|
|