| Автор: | Жюри летних сборов 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 | |
|