Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

F. Туристическая реформа
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Берляндия — туристическая страна! Во всяком случае, она такой может стать — уверено правительство Берляндии.

Берляндия состоит из n городов, некоторые пары которых соединены двусторонними дорогами. Каждая дорога соединяет два различных города. В Берляндии нет дорог, соединяющих одинаковую пару городов. Из любого города можно добраться до любого другого по заданным двусторонним дорогам.

В соответствии с новой реформой каждая дорога будет превращена в одностороннюю — ориентирована в одну из двух сторон.

Чтобы максимизировать туристическую привлекательность Берляндии для каждого города i после реформы будет подсчитана величина ri — количество таких городов x, что из города i существует ориентированный путь до города x. Иными словами, ri равно количеству городов, в которые можно добраться из города i, следуя по дорогам.

Правительство уверено, что внимание туристов будет сконцентрировано на минимальном из ri.

Помогите правительству Берляндии провести реформу так, чтобы максимизировать минимальное из ri.

Входные данные

Первая строка содержит два целых числа n, m (2 ≤ n ≤ 400 000, 1 ≤ m ≤ 400 000) — количество городов и количество дорог соответственно.

Далее следуют m строк, описывающие дороги в Берляндии: j-я из них содержит два целых числа uj и vj (1 ≤ uj, vj ≤ n, uj ≠ vj), где uj и vj — номера городов, которые соединены j-й дорогой.

Считайте, что города пронумерованы от 1 до n. Гарантируется, что из любого города можно добраться до любого другого по заданным двусторонним дорогам. В Берляндии нет дорог, соединяющих одинаковую пару городов.

Выходные данные

Первая строка должна содержать одно целое число — максимальное возможное значение min1 ≤ i ≤ n{ri} после ориентации всех дорог.

Следующие m строк должны содержать описание дорог после ориентации: j-я из них должна содержать два целых числа uj, vj, означающих, что j-я дорога ведет из города uj в город vj. Дороги следует выводить в том же порядке, в котором они заданы во входных данных.

Пример
Входные данные
7 9
4 3
2 6
7 1
4 1
7 3
3 5
7 4
6 5
2 5
Выходные данные
4
4 3
6 2
7 1
1 4
3 7
5 3
7 4
5 6
2 5