Codeforces Round 962 (Div. 3) |
---|
Закончено |
На Пенаконии, земле грёз существует $$$n$$$ домов и $$$n$$$ дорог. Существует дорога между домом $$$i$$$ и $$$i+1$$$ для всех $$$1 \leq i \leq n-1$$$ и дорога между домом $$$n$$$ и домом $$$1$$$. Все дороги двусторонние. Однако из-за кризиса на Пенаконии, управляющая семья залезла в долги и может не быть в состоянии поддерживать все дороги.
Среди жителей Пенаконии существует $$$m$$$ пар друзей. Если житель, живущий в доме $$$a$$$, дружит с жителем, живущим в доме $$$b$$$, должен существовать путь между домами $$$a$$$ и $$$b$$$ через поддерживаемые дороги.
Какое минимальное количество дорог для этого необходимо поддержать?
Первая строка содержит $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество тестов.
Первая строка каждого теста содержит два целых числа $$$n$$$ и $$$m$$$ ($$$3 \leq n \leq 2 \cdot 10^5, 1 \leq m \leq 2 \cdot 10^5$$$) — количество домов и количество дружб.
Следующие $$$m$$$ строк содержат два целых числа $$$a$$$ и $$$b$$$ ($$$1 \leq a < b \leq n$$$) — житель дома $$$a$$$ дружит с жителем дома $$$b$$$. Гарантируется, что все ($$$a, b$$$) различны.
Гарантируется, что сумма $$$n$$$ и $$$m$$$ по всем тестам не превышает $$$2 \cdot 10^5$$$.
Для каждого теста выведите целое число — минимальное количество дорог, которые должны быть поддержаны.
78 31 82 74 513 41 132 123 114 1010 22 33 410 43 85 102 104 104 11 35 23 51 45 22 51 3
4 7 2 7 2 3 3
В первом примере должны быть поддержаны следующие дороги:
Название |
---|