Свободное перемещение
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

ПодзадачаБаллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
118$$$m \leqslant 20$$$полная
218 каждая локация связана не более, чем с двумя другими локациями полная
320$$$m = \frac{n \cdot (n - 1)}{2}$$$полная
416 между любыми двумя локациями существует единственный путь (граф города — дерево) полная
528нет1–4первая ошибка

Примеры

Входные данные
3 2
1 2
1 3
Выходные данные
1
1 2
3 1
Входные данные
4 5
1 2
1 3
2 3
1 4
3 4
Выходные данные
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)$$$.