Дороги та міста
Обмеження: 1 сек., 256 МіБ
У країнi, де є n мiст, пронумерованих вiд 1 до n включно, буде побудовано m дорiг. Кожна дорога сполучає між собою пару різних міст.
Після кожної побудованої дороги треба визначити кількість компонент зв’язності.
Вхідні дані
У першому рядку задано два цілих числа \(n\) і \(m\) — кількість міст в країні та кількість доріг, що збудують, відповідно.
У наступних \(m\) рядках задано по два цілих числа \(a\) і \(b\) — номери двох різних міст між якими будується відповідна дорога.
Вихідні дані
Виведіть \(m\) рядків — кількість компонент зв’язності після кожної побудованої дороги.
Обмеження
\(2 \le n, m \le 10^5\),
\(1 \le a, b \le n\),
\(a \ne b\).
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
4 5 1 2 4 3 2 4 2 3 1 3 | 3 2 1 1 1 |
Джерело: Прості задачі
Надіслати розв'язок
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|