Тюремні перестановки#3500
Щоб зменшити ризик бунтів і спроб втечі, керівництва двох сусідніх в’язниць однакової місткості вирішили перерозподілити між собою ув’язнених. Вони хочуть обміняти половину ув’язнених однієї в’язниці на половину ув’язнених іншої. Однак, із заархівованих даних про кримінальне минуле ув’язнених відомо, що певні пари ув’язнених є небезпечними для спільного утримання в одній установі. Тому для кожної такої пари одного ув’язненого розміщують у першій в’язниці, а іншого — у другій. Керівництва погоджуються, що таких пар не можна тримати разом, тому завдання ускладнюється. Насправді вони швидко з’ясовують, що іноді неможливо здійснити обмін рівно половиною ув’язнених, дотримуючись цієї вимоги. Якщо таке трапляється, їм доводиться обмінювати якомога ближче до половини ув’язнених.
Перший рядок вхідних даних містить одне додатне число , що означає кількість тестових сценаріїв. Кожен сценарій починається з рядка з двома цілими числами та , де 1 < m < 200 ( — кількість ув’язнених у кожній із двох в’язниць), а — кількість небезпечних пар серед ув’язнених. Далі слідують рядків, кожний з яких містить пару чисел x_i y_i в діапазоні від до , що означає: ув’язненого x_i з першої в’язниці не можна утримувати в одній установі з ув’язненим y_i з другої в’язниці.
Для кожного тестового сценарію виведіть один рядок із найбільшим цілим числом (k \leq \frac{m}{2}), таким, що можна обміняти ув’язнених із першої в’язниці на ув’язнених із другої, не помістивши жодної небезпечної пари разом.
Приклад 1