D. Чередующийся путь
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан неориентированный граф из $$$n$$$ вершин и $$$m$$$ ребёр. Вершины пронумерованы от $$$1$$$ до $$$n$$$. В графе отсутствуют петли и кратные рёбра.

Ваша задача — ориентировать каждое ребро. После ориентации ребер назовем последовательность вершин $$$v_1, v_2, \dots, v_k$$$, где $$$k$$$ может быть любым и любая вершина может повторяться сколько угодно раз, чередующимся путем, если:

  • ребро $$$(v_1, v_2)$$$ ориентировано от $$$v_1$$$ к $$$v_2$$$;
  • ребро $$$(v_2, v_3)$$$ ориентировано от $$$v_3$$$ к $$$v_2$$$;
  • ребро $$$(v_3, v_4)$$$ ориентировано от $$$v_3$$$ к $$$v_4$$$;
  • ребро $$$(v_4, v_5)$$$ ориентировано от $$$v_5$$$ к $$$v_4$$$;
  • и так далее.

Назовем вершину $$$v$$$ красивой, если все пути (не обязательно простые) в исходном графе, которые начинаются в вершине $$$v$$$, являются чередующимися в полученном ориентированном графе.

Какое наибольшее количество красивых вершин можно получить после ориентации ребер?

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

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

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

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

Дополнительные ограничения на входные данные:

  • Заданный граф не содержит петель и кратных ребер;
  • Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$;
  • Сумма $$$m$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Выходные данные

На каждый набор входных данных выведите одно целое число — наибольшее количество красивых вершин, которое можно получить после ориентации ребер.

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