На Пенаконии, земле грёз существует \(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\).
Для каждого теста выведите целое число — минимальное количество дорог, которые должны быть поддержаны.
В первом примере должны быть поддержаны следующие дороги:
7 8 3 1 8 2 7 4 5 13 4 1 13 2 12 3 11 4 10 10 2 2 3 3 4 10 4 3 8 5 10 2 10 4 10 4 1 1 3 5 2 3 5 1 4 5 2 2 5 1 3
4 7 2 7 2 3 3
3000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач