Берляндия — туристическая страна! Во всяком случае, она такой может стать — уверено правительство Берляндии.
Берляндия состоит из n городов, некоторые пары которых соединены двусторонними дорогами. Каждая дорога соединяет два различных города. В Берляндии нет дорог, соединяющих одинаковую пару городов. Из любого города можно добраться до любого другого по заданным двусторонним дорогам.
В соответствии с новой реформой каждая дорога будет превращена в одностороннюю — ориентирована в одну из двух сторон.
Чтобы максимизировать туристическую привлекательность Берляндии для каждого города i после реформы будет подсчитана величина ri — количество таких городов x, что из города i существует ориентированный путь до города x. Иными словами, ri равно количеству городов, в которые можно добраться из города i, следуя по дорогам.
Правительство уверено, что внимание туристов будет сконцентрировано на минимальном из ri.
Помогите правительству Берляндии провести реформу так, чтобы максимизировать минимальное из ri.
Выходные данные
Первая строка должна содержать одно целое число — максимальное возможное значение min1 ≤ i ≤ n{ri} после ориентации всех дорог.
Следующие m строк должны содержать описание дорог после ориентации: j-я из них должна содержать два целых числа uj, vj, означающих, что j-я дорога ведет из города uj в город vj. Дороги следует выводить в том же порядке, в котором они заданы во входных данных.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|