В Берляндии есть n городов и m двунаправленных дорог, которыми соединены некоторые пары городов. Известно, что между каждой парой городов существует не более одной дороги, а также никакая дорога не соединяет город сам с собой. Допустимо, что между некоторыми парами городов не существует пути по дорогам от одного до другого.
Дорожный министр решил провести в Берляндии реформу и заориентировать все дороги в стране, то есть сделать каждую дорогу односторонней. При этом министр хочет максимизировать количество таких городов, чтобы количество дорог, начинающихся в этих городах, было равно количеству дорог, которые в них заканчиваются.
В первой строке следует целое положительное число t (1 ≤ t ≤ 200) — количество наборов входных данных.
Каждый из наборов входных данных задаётся следующим образом. В первой строке следует два целых числа n и m (1 ≤ n ≤ 200, 0 ≤ m ≤ n·(n - 1) / 2) — количество городов и количество дорог в Берляндии.
В следующих m строках следует описание дорог в Берляндии. В каждой строке находятся по два целых числа u и v (1 ≤ u, v ≤ n) — номера городов, которые соединяет очередная дорога. Гарантируется, что никакая дорога не соединяет город с самим самой и между любой парой городов существует не более одной дороги. Допустимо, что между некоторыми парами городов не существует пути по дорогам от одного до другого.
Гарантируется, что суммарное количество городов во всех наборах входных данных не превосходит 200.
Обратите внимание, что для взломов вы можете использовать только тесты, состоящие из одного набора входных данных, то есть t должно быть равно единице.
Для каждого набора входных данных выведите сначала искомое максимальное количество таких городов, что количество дорог, начинающихся в этих городах, было равно количеству дорог, которые в них заканчиваются.
В следующих m строках выведите заориентированные дороги. Сначала выводите номер города, в котором дорога начинается, а затем номер города, в котором дорога заканчивается. Если ответов несколько, выведите любой из них. Дороги в каждом наборе входных данных разрешается выводить в любом порядке. Каждая дорога должна быть выведена ровно один раз.
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
| Codeforces Round 375 (Div. 2) |
|---|
| Закончено |
