| Финал ВКОШП.Junior 2026 |
|---|
| Finished |
Панды утверждают, что лучший путь к совершенству — сделать четыре шага и снова оказаться там, где начал.
В мире животных тоже бывают необычные увлечения. Например, капибара Валера решил всерьёз заняться искусством лени. По слухам, настоящими мастерами этого дела являются панды из Китая, поэтому Валера отправился в путешествие, чтобы изучить их философию спокойствия.
В Китае существует множество уютных локаций: бамбуковые рощи, тихие чайные сады, каменные мостики и павильоны для медитации. Некоторые локации соединены направленными тропинками. Каждая тропинка ведёт из одной локации в другую и имеет свой номер.
Валера хочет устроить тренировку: пройти ровно четыре различных тропинки подряд и снова вернуться в исходную локацию. Такой маршрут помогает капибарам лучше почувствовать циклическую природу лени — немного пройтись, посмотреть на бамбук и снова оказаться там, где начинал.
Локации пронумерованы целыми числами от $$$1$$$ до $$$n$$$. Всего существует $$$m$$$ направленных тропинок. $$$i$$$-я тропинка имеет вид ($$$x_i, y_i$$$), что означает наличие направленной тропинки из локации $$$x_i$$$ в локацию $$$y_i$$$.
Валера хочет выбрать четыре различных тропинки $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$, такие что если пройти по тропинкам $$$a \rightarrow b \rightarrow c \rightarrow d$$$, получится замкнутый маршрут длины $$$4$$$. Тропинки считаются различными по их индексам, даже если они соединяют одни и те же локации.
Помогите Валере узнать, сколько существует допустимых четвёрок тропинок ($$$a, b, c, d$$$).
В первой строке заданы два целых числа $$$n$$$ и $$$m$$$ — количество локаций и количество тропинок ($$$1 \le n, m \le 5000$$$).
В следующих $$$m$$$ строках содержатся по два целых числа $$$x_i$$$ и $$$y_i$$$ — начало и конец $$$i$$$-й направленной тропинки ($$$1 \le x_i, y_i \le n$$$).
Выведите одно целое число — количество допустимых четвёрок тропинок ($$$a, b, c, d$$$)
5 6 1 2 2 3 3 4 4 1 1 5 5 3
8
2 4 1 2 1 2 2 1 2 1
8
Во втором тесте Валера может начать прогулку из локации 1 или из локации 2, для каждой из них возможно 4 варианта.
[1, 3, 2, 4], [1, 4, 2, 3],[2, 3, 1, 4], [2, 4, 1, 3], [3, 2, 4, 1, [4, 2, 3, 1],[3, 1, 4, 2], [4, 1, 3, 2]
| Name |
|---|


