В Берляндии есть n городов и m двунаправленных дорог, которыми соединены некоторые пары городов. Известно, что между каждой парой городов существует не более одной дороги, а также никакая дорога не соединяет город сам с собой. Допустимо, что между некоторыми парами городов не существует пути по дорогам от одного до другого.
Дорожный министр решил провести в Берляндии реформу и заориентировать все дороги в стране, то есть сделать каждую дорогу односторонней. При этом министр хочет максимизировать количество таких городов, чтобы количество дорог, начинающихся в этих городах, было равно количеству дорог, которые в них заканчиваются.
Выходные данные
Для каждого набора входных данных выведите сначала искомое максимальное количество таких городов, что количество дорог, начинающихся в этих городах, было равно количеству дорог, которые в них заканчиваются.
В следующих m строках выведите заориентированные дороги. Сначала выводите номер города, в котором дорога начинается, а затем номер города, в котором дорога заканчивается. Если ответов несколько, выведите любой из них. Дороги в каждом наборе входных данных разрешается выводить в любом порядке. Каждая дорога должна быть выведена ровно один раз.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
5 5
2 1
4 5
2 3
1 3
3 5
7 2
3 7
4 2
|
3
1 3
3 5
5 4
3 2
2 1
3
2 4
3 7
|