На Пенаконии, земле грёз существует \(n\) домов и \(n\) дорог. Существует дорога между домом \(i\) и \(i+1\) для всех \(1 \leq i \leq n-1\) и дорога между домом \(n\) и домом \(1\). Все дороги двусторонние. Однако из-за кризиса на Пенаконии, управляющая семья залезла в долги и может не быть в состоянии поддерживать все дороги.
Среди жителей Пенаконии существует \(m\) пар друзей. Если житель, живущий в доме \(a\), дружит с жителем, живущим в доме \(b\), должен существовать путь между домами \(a\) и \(b\) через поддерживаемые дороги.
Какое минимальное количество дорог для этого необходимо поддержать?
Выходные данные
Для каждого теста выведите целое число — минимальное количество дорог, которые должны быть поддержаны.
Примечание
В первом примере должны быть поддержаны следующие дороги:
- \(8 \leftarrow \rightarrow 1\)
- \(7 \leftarrow \rightarrow 8\)
- \(1 \leftarrow \rightarrow 2\)
- \(4 \leftarrow \rightarrow 5\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|