Мальчик Коля любит графы, но не любит циклы. У Коли есть несколько ориентированных не обязательно связных
графов. Графы могут содержать параллельные ребра, но не содержат петли. К сожалению, некоторые из них могут содержать
циклы.
Коля хочет развернуть некоторые ребра в каждом графе, чтобы избавиться от циклов. Разворотом ребра будем считать
замену ребра из вершины a в вершину b на противоположное ребро, которое будет направлено из вершины b в вершину a. При
этом Коля хочет развернуть наименьшее число ребер в каждом графе, чтобы получившиеся графы не содержали циклов.
Помогите Коле узнать, какое наименьшее число ребер ему нужно развернуть в каждом графе.
Входные данные
В первой строке входных данных содержится число t - число графов (1≤t≤8).
В первой строке описания каждого графа дано два числа n и m - число вершин и число ребер соответственно
(2≤n≤10, 1≤m≤1000).
В следующих m строках содержатся пары чисел a
i, b
i - описание ребер графа (1≤ a
i, b
i ≤ n, a
i ≠ b
i).
Для удобства, описания графов разделены пустыми строками. Пустой строки после последнего графа нет.
Гарантируется, что суммарное число вершин во всех графах не превосходит 50.
Выходные данные
Для каждого графа выведите одно число в отдельной строке - наименьшее число ребер, которые нужно развернуть, чтобы полученный граф не содержал циклов.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
4
2 2
1 2
2 1
4 2
1 4
4 3
3 3
1 2
2 3
3 1
3 5
1 2
2 3
3 1
2 3
1 3 |
1
0
1
1 |
Замечание
В первом графе нужно развернуть одно из ребер, чтобы убрать цикл. Во втором графе циклов изначально нет, так что
ничего разворачивать не надо. В третьем графе можно развернуть любое ребро, чтобы убрать цикл. В четвертом графе нужно
развернуть ребро (3,1) или ребро (1,2), чтобы новый граф не содержал циклов.