Минимизация ребер
Минимизация ребер
У Беси есть связный ненаправленный граф G с n вершинами, помеченными 1..n и m ребрами. G может содержать петли (ребра из вершины в неё же), но не имеет параллельных ребер (несколько ребер, соединяющих одни и те же конечные точки).
Пусть fG(a, b) это булевская функция, которая отвечает истина, если существует путь от вершины 1 до вершины a, который проходит ровно b ребер, для 1 ≤ a ≤ n и 0 ≤ b и ложь иначе. Если по ребру проходим множество раз, это число включается в ответ.
Эльза хочет копировать Беси. В частности, она хочет сконструировать ненаправленный граф G′ такой, что fG′(a, b) = fG(a, b) для всех a и b.
Эльза хочет сделать минимальное количество работы, поэтому она хочет сконструировать минимально возможный граф. Ваша задача - вычислить минимально возможное количество ребер в G′.
Каждый ввод содержит t тестов, которые должны решаться независимо. Гарантируется, что сумма n по всем тестам не превысит 105
, а сумма m по всем тестам не превысит 2 * 105
.
Входные данные
Первая строка ввода содержит количество тестов t (1 ≤ t ≤ 5 * 104
).
Первая строка каждого теста содержит два целых числа n и m (2 ≤ n ≤ 105
, n − 1 ≤ m ≤ (n2
+ n) / 2.
Следующие m строк каждого теста содержат два целых числа x и y (1 ≤ x ≤ y ≤ n), обозначающих ребро между x и y в G.
Последовательные тесты разделены пустой строй для читабельности.
Выходные данные
Для каждого теста выведите минимально возможное количество ребер в G′ в отдельной строке.
Пример
В первом тесте, Эльза может сконструировать G′, начав с G и удалив ребро (2, 5). Или может сконструировать граф со следующим ребрами
1 2
1 4
4 3
4 5
поскольку она не ограничена только удалением ребер из G: Эльза определенно не может сделать меньше чем n − 1 ребро, поскольку граф G′ также должен быть связным.
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
4 5