G. Пенакония
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На Пенаконии, земле грёз существует $$$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
Примечание

В первом примере должны быть поддержаны следующие дороги:

  • $$$8 \leftarrow \rightarrow 1$$$
  • $$$7 \leftarrow \rightarrow 8$$$
  • $$$1 \leftarrow \rightarrow 2$$$
  • $$$4 \leftarrow \rightarrow 5$$$