시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB111100.000%

문제

Эйден Колдуолл обладает довольно большим количеством навыков и способностей, среди которых прекрасное владение паркуром. Город Вилледор, в котором Эйден сейчас находится, состоит из $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

3 2
1 2
1 3

예제 출력 1

1
1 2
3 1

예제 입력 2

4 5
1 2
1 3
2 3
1 4
3 4

예제 출력 2

6
1 2
2 3
3 1
1 4
4 3

노트

В первом примере всего три локации, связанные двумя переходами. Максимальный возможный ответ равен $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)$.