Існує \(n\) міст, між якими спочатку немає доріг. Проте кожен день будуватиметься нова дорога, а загалом буде \(m\) доріг.

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

Обмеження

• \(1≤n≤10^5\)
• \(1≤m≤2⋅10^5\)
• \(1≤ a,b≤n\)

Формат вхідних даних

У першому рядку є два цілі числа \(n\) і \(m\): кількість міст і доріг. Міста пронумеровані цифрами \(1,2,…,n\).

Потім є \(m\) рядків, що описують нові дороги. Кожен рядок містить два цілі числа \(a\) і \(b\): будується нова дорога між містами \(a\) і \(b\). Ви можете припустити, що кожна дорога буде побудована між двома різними містами.

Формат вихідних даних

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

Приклад вхідних даних

5 3
1 2
1 3
4 5

Приклад вихідних даних

4 2
3 3
2 3