Statement is not available in English language
C. Судьба
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Эмия Кирицугу потерял своего верного слугу в тяжёлой схватке и сейчас пытается укрыться в семейном поместье Айнцберн. В нём $$$n$$$ комнат, которые соединены $$$m$$$ коридорами.

Великий царь Гильгамеш преследует Эмию и уже добрался до его поместья. За один час Гильгамеш одновременно уничтожает все комнаты из которых выходит наибольшее количество коридоров. Вместе в комнатой уничтожаются все коридоры, которыми она была связана с какими-то другими комнатами.

Эмия Кирицугу очень устал, поэтому хочет перевести силы перед битвой с Гильгамешем. Другими словами, он хочет прятаться как можно дольше, поэтому заранее выберет одну из комнат, которую Гильгамеш уничтожит последней.

Помогите Кирицугу определить, какое максимальное количество часов он сможет прятаться от Гильгамеша.

Входные данные

В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

В первой строке каждого набора даны целые числа $$$n$$$, $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 2 \cdot 10^5$$$) — количество комнат и коридоров соответственно.

В следующих $$$m$$$ строках каждого набора даны целые числа $$$v$$$, $$$u$$$ ($$$1 \le v, u \le n$$$, $$$v \neq u$$$) — комнаты, соединённые соответствующим коридором.

Между одной парой комнат могут быть несколько коридоров. Кроме того, не гарантируется, что существует путь по коридорам между каждой парой комнат.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$. То же самое гарантируется для $$$m$$$.

Выходные данные

Для каждого набора входных данных выведите единственное целое число — максимальное количество часов, которое сможет прятаться Эмия Кирицугу.

Пример
Входные данные
2
5 7
3 2
1 4
4 5
4 3
5 2
3 1
2 3
2 1
1 2
Выходные данные
3
1