Дорожнє будівництво

У нас є n міст, між якими спочатку немає жодної дороги. Однак щодня буде збудовано нову дорогу, і загалом буде збудовано m доріг.

Компонента зв'язності - це група міст, між якими існує маршрут через дороги. Після кожного дня вам потрібно визначити кількість компонент зв'язності та розмір найбільшої з них.

Вхідні дані

У першому рядку подано два цілі числа n (1 ≤ n ≤ 10^5) та m (1 ≤ m ≤ 2 * 10^5): кількість міст і доріг. Міста пронумеровані від 1 до n.

Наступні m рядків описують нові дороги. Кожен рядок містить два цілі числа a та b (1 ≤ a, b ≤ n): нова дорога з'єднує міста a та b.

Кожна нова дорога з'єднує два різні міста.

Вихідні дані

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

Приклади