eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Спільний предок

Спільний предок

Задано орієнтовний граф. Підрахуйте, скільки пар вершин $(i, j)$ мають спільного предка. Спільним предком вершин $i$ та $j$ називається така вершина $k$, що $i$ та $j$ досяжні з $k$. \InputFile У першому рядку містяться цілі числа $n$ та $m~(1 \le n \le 10^4, 0 \le m \le 10^4)$ --- кількість вершин та ребер у графі. Далі йде $m$ рядків по два числа від $1$ до $n$ у кожному. Пара чисел $(a, b)$ позначає, що з вершини $a$ є ребро у вершину $b$. \OutputFile Виведіть одне число --- кількість пар. \includegraphics{https://eolympusercontent.com/images/qrgvlfh2t533500f3smc7q8pic.gif}
Ліміт часу 2 секунди
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
2 1
1 2
Вихідні дані #1
4
Вхідні дані #2
3 2
2 1
3 1
Вихідні дані #2
7