26691번 - Trzy drogi 다국어

Król Bajtur, władca Bajtocji, lubi śnić o podboju Bitocji. Przyjemnie jest pomarzyć o pokonaniu przeciwnika, jednak życie to nie sen i na jawie sytuacja wygląda nieco inaczej.

Bajtocja składa się z n miast (ponumerowanych liczbami od 1 do n) połączonych m dwukierunkowymi drogami. Każda droga łączy dwa różne miasta, ale może się zdarzyć, że wiele dróg łączy tę samą parę miast. Z każdego miasta da się dojechać do każdego innego, być może korzystając z wielu dróg.

Król zastanawia się, co by było, gdyby Bitocja zaatakowała Bajtocję i zniszczyła trzy drogi spośród m istniejących. Jakie są szanse, że poważnie zaszkodzi to komunikacji w kraju? Twoim zadaniem jest to stwierdzić! Policz, ile istnieje takich trójek dróg, po których zniszczeniu będzie istniała chociaż jedna para miast, między którymi nie będzie się dało przejechać, korzystając z pozostałych dróg.

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite n oraz m (2 ≤ n ≤ 200 000, 3 ≤ m ≤ 500 000) oznaczające odpowiednio liczbę miast oraz liczbę dróg w Bajtocji.

W kolejnych m wierszach znajdują się opisy dróg; i-ty z tych wierszy zawiera dwie liczby całkowite a_i i b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i) oznaczające, że i-ta droga łączy miasta o numerach a_i oraz b_i.

Możesz założyć, że sieć dróg pozwala na dotarcie z każdego miasta do każdego innego.

Na wyjściu powinna znaleźć się jedna liczba całkowita, równa liczbie takich nieuporządkowanych trójek dróg, że po ich usunięciu będą istniały co najmniej dwa miasta, między którymi nie będzie się dało przejechać.

Wyjaśnienie przykładu: Zwróć uwagę, że po usunięciu np. trzeciej, piątej i siódmej drogi Bajtocja rozpadnie się na więcej niż dwie części. Mimo to, taka trójka krawędzi powinna zostać policzona tylko raz.