Имеются n городов, между которыми изначально нет дорог. Однако каждый день будет строиться новая дорога, а всего будет построено m дорог.

Компонента связности - это группа городов, между любыми двумя из которых существует маршрут по дорогам. После каждого дня Вам следует найти количество компонент связности и размер наибольшей компоненты.

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

В первой строке заданы два целых числа n (1 ≤ n ≤ 105) и m (1 ≤ n ≤ 2 * 105): количество городов и дорог. Города пронумерованы 1, 2, ..., n.

Следующие m строк описывают новые дороги. Каждая строка содержит два целых числа a и b (1 ≤ a, b ≤ n): новая дорога строится между городами a и b.

Каждая новая дорога строится между двумя разными городами.

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

Выведите m строк: необходимую информацию после каждого дня.