Тюремные перестановки
Для того, чтобы снизить риск беспорядков и попыток побега, администрации двух соседних тюрем равной вместительности по содержанию заключённых, решили поменять своих заключенных между собой. Они хотят обменять половину заключенных одной из тюрем, с половиной заключенных из другой. Однако, из архивной информации об истории преступлений заключенных, они знают, что некоторые пары заключенных опасно содержать в одной и той же тюрьме, и именно поэтому они содержаться отдельно сейчас, т. е. для каждой такой пары заключенных, один из заключенных отбывает свой срок в первой тюрьме, а другой - во второй. Администрации договорились о необходимости содержания этих пар раздельно в разных тюрьмах, что делает задачу попыток совершения обменов немного сложнее. В самом деле, скоро они обнаружат, что иногда невозможно выполнить все желаемые замены для половины заключенных. Всякий раз, когда такое происходит, они должны согласиться на обмен, который находиться как можно ближе к половине обмена заключенными насколько это возможно.
Входные данные
В первой строке входного файла задано одно натуральное число n, указывающее на количество последующих тестовых сценариев. Каждый тестовый сценарий начинается со строки, содержащей два целых неотрицательных чисел m и r, 1 < m < 200 - является количеством заключенных в каждой из двух тюрем, а r - число опасных пар среди заключенных. Затем следует r строк, каждая из которых содержит пару x_i y_i целых чисел в диапазоне от 1 до r, означающих, что заключенный x_i первой тюрьмы не должен быть помещен в ту же тюрьму, что и узник y_i второй тюрьмы.
Выходные данные
Для каждого тестового сценария выведите одну строку, содержащую наибольшее целое число k ≤ m/2, такое, что можно обменять k заключенных первой тюрьмы с k заключенными второй тюрьмы без получения двух заключенных из любой опасной пары в одной и той же тюрьме.