У Bessie есть связный неориентированный граф $G$ с $N$ вершинами, пронумерованными $1\ldots N$, и $M$ рёбрами ($2\le N\le 10^5, N-1\le M\le \frac{N^2+N}{2}$). В $G$ могут быть петли (рёбра, соединяющие вершину с самой собой), но нет кратных рёбер (нескольких рёбер, соединяющих одни и те же концы).
Пусть $f_G(a,b)$ — булева функция, которая для каждого $1\le a\le N$ и $0\le b$ принимает значение «истина», если существует путь из вершины $1$ в вершину $a$, проходящий ровно по $b$ рёбрам, и «ложь» в противном случае. Если ребро проходится несколько раз, оно учитывается в подсчёте столько же раз.
Elsie хочет скопировать Bessie. В частности, она хочет построить неориентированный граф $G'$ такой, что $f_{G'}(a,b)=f_G(a,b)$ для всех $a$ и $b$.
Elsie хочет выполнить как можно меньше работы, поэтому хочет построить как можно меньший граф. Следовательно, ваша задача — вычислить минимально возможное количество рёбер в $G'$.
Каждый входной файл содержит $T$ ($1\le T\le 5\cdot 10^4$) тестовых случаев, которые следует решать независимо. Гарантируется, что сумма $N$ по всем тестовым случаям не превосходит $10^5$, а сумма $M$ по всем тестовым случаям не превосходит $2\cdot 10^5$.
Входные данные
Первая строка входных данных содержит $T$ — количество тестовых случаев.
Первая строка каждого тестового случая содержит два целых числа $N$ и $M$.
Каждая из следующих $M$ строк каждого тестового случая содержит два целых числа $x$ и $y$ ($1\le x\le y\le N$), обозначающих наличие ребра между $x$ и $y$ в $G$.
Для удобства чтения последовательные тестовые случаи разделены пустыми строками.
Выходные данные
Для каждого тестового случая выведите в новой строке минимально возможное количество рёбер в $G'$.
Примеры
Входные данные 1
2
5 5
1 2
2 3
2 5
1 4
4 5
5 5
1 2
2 3
3 4
4 5
1 5Выходные данные 1
4
5Примечание
В первом тестовом случае Elsie может построить $G'$, взяв $G$ и удалив $(2,5)$. Или она может построить граф со следующими рёбрами, поскольку она не ограничена только удалением рёбер из $G$:
1 2 1 4 4 3 4 5
Elsie определённо не может получить меньше $N-1$ рёбер, поскольку $G'$ также должен быть связным.
Входные данные 2
7
8 10
1 2
1 3
1 4
1 5
2 6
3 7
4 8
5 8
6 7
8 8
10 11
1 2
1 5
1 6
2 3
3 4
4 5
4 10
6 7
7 8
8 9
9 9
13 15
1 2
1 5
1 6
2 3
3 4
4 5
6 7
7 8
7 11
8 9
9 10
10 11
11 12
11 13
12 13
16 18
1 2
1 7
1 8
2 3
3 4
4 5
5 6
6 7
8 9
9 10
9 15
9 16
10 11
11 12
12 13
13 14
14 15
14 16
21 22
1 2
1 9
1 12
2 3
3 4
4 5
5 6
6 7
7 8
7 11
8 9
8 10
12 13
13 14
13 21
14 15
15 16
16 17
17 18
18 19
19 20
20 21
20 26
1 2
1 5
1 6
2 3
3 4
4 5
4 7
6 8
8 9
8 11
8 12
8 13
8 14
8 15
8 16
8 17
9 10
10 18
11 18
12 19
13 20
14 20
15 20
16 20
17 20
19 20
24 31
1 2
1 7
1 8
2 3
3 4
4 5
5 6
6 7
6 9
8 10
10 11
10 16
10 17
10 18
10 19
10 20
11 12
12 13
13 14
14 15
15 16
15 17
15 18
15 19
15 20
15 21
15 22
15 23
15 24
21 22
23 24Выходные данные 2
10
11
15
18
22
26
31Примечание
В каждом из этих тестовых случаев Elsie не может получить лучший результат, чем Bessie.
- Все тестовые случаи во входном файле 3 удовлетворяют $N\le 5$.
- Все тестовые случаи во входных файлах 4–5 удовлетворяют $M=N$.
- Для всех тестовых случаев во входных файлах 6–9, если не выполняется равенство $f_G(x,b)=f_G(y,b)$ для всех $b$, то существует $b$, для которого $f_G(x,b)$ истинно, а $f_G(y,b)$ ложно.
- Все тестовые случаи во входных файлах 10–15 удовлетворяют $N\le 10^2$.
- Для тестовых случаев во входных файлах 16–20 нет дополнительных ограничений.
Автор задачи: Benjamin Qi