Эйден Колдуолл обладает довольно большим количеством навыков и способностей, среди которых прекрасное владение паркуром. Город Вилледор, в котором Эйден сейчас находится, состоит из $$$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 | 18 | $$$m \leqslant 20$$$ | полная | |
2 | 18 | каждая локация связана не более, чем с двумя другими локациями | полная | |
3 | 20 | $$$m = \frac{n \cdot (n - 1)}{2}$$$ | полная | |
4 | 16 | между любыми двумя локациями существует единственный путь (граф города — дерево) | полная | |
5 | 28 | нет | 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)$$$.