Имеются n городов, между которыми изначально нет дорог. Однако каждый день будет строиться новая дорога, а всего будет построено m дорог.
Компонента связности - это группа городов, между любыми двумя из которых существует маршрут по дорогам. После каждого дня Вам следует найти количество компонент связности и размер наибольшей компоненты.
В первой строке заданы два целых числа n (1 ≤ n ≤ 10^5
) и m (1 ≤ n ≤ 2 * 10^5
): количество городов и дорог. Города пронумерованы 1, 2, ..., n.
Следующие m строк описывают новые дороги. Каждая строка содержит два целых числа a и b (1 ≤ a, b ≤ n): новая дорога строится между городами a и b.
Каждая новая дорога строится между двумя разными городами.
Выведите m строк: необходимую информацию после каждого дня.