Свободное перемещение

Эйден Колдуолл обладает довольно большим количеством навыков и способностей, среди которых прекрасное владение паркуром. Город Вилледор, в котором Эйден сейчас находится, состоит из $n$ локаций и $m$ двухсторонних переходов для паркура между ними; $i$-й переход соединяет локации под номерами $u\_i$ и $v\_i$.

Чтобы иметь возможность быстро перемещаться между локациями, Эйден может установить на каждом переходе специальное снаряжение, которое позволит ему перемещаться в одну сторону заметно быстрее, чем в другую. Эйден считает удобной любую тройку локаций $a$, $b$ и $c$ такую, что из $a$ в $b$ доступно быстрое перемещение и из $b$ в $c$ доступно быстрое перемещение.

Помогите Эйдену установить специальное снаряжение на каждом переходе, чтобы максимизировать количество удобных троек. Обратите внимание, что для каждого перехода надо выбрать ровно одно направление из двух, в котором перемещение будет быстрым.

В первой строке входных данных дано два целых числа $n$ и $m$ --- количество локаций и переходов между ними ($2 \leqslant n \leqslant 3 \cdot 10^5; 1 \leqslant m \leqslant 3 \cdot 10^5$).

В $i$-й из следующих $m$ строк через пробел даны два целых числа $u\_i$ и $v\_i$ --- номера локаций, между которыми пролегает $i$-й переход ($1 \leqslant u\_i, v\_i \leqslant n$; $u\_i \neq v\_i$). Гарантируется, что никакие два перехода не соединяют одни и те же две локации.

В первой строке выходных данных выведите целое число $ans$ --- максимально возможное количество удобных троек локаций, которого можно добиться.

В следующих $m$ строках выведите описание направлений для быстрого перемещения. В $i$-й строке выведите через пробел два целых числа $x\_i$ и $y\_i$ ($1 \leqslant x\_i, y\_i \leqslant n$), обозначающие, что перемещение между локациями $x\_i$ и $y\_i$ будет быстрым по направлению от $x\_i$ к $y\_i$, а не наоборот.

Порядок вывода переходов может быть произвольным и не обязан совпадать с порядком переходов во вводе.

Если есть несколько способов расставить направления для быстрого перемещения, приводящих к максимальному количеству удобных троек локаций, выведите любой из них.

В первом примере всего три локации, связанные двумя переходами. Максимальный возможный ответ равен $1$, и чтобы его добиться, достаточно ориентировать переходы так, чтобы все три локации образовывали удобную тройку.

Во втором примере $6$ удобных троек --- это $(1 \to 2 \to 3)$, $(2 \to 3 \to 1)$, $(3 \to 1 \to 2)$, $(1 \to 4 \to 3)$, $(4 \to 3 \to 1)$ и $(3 \to 1 \to 4)$.