В уже известной нам некоторой большой корпорации, в которой работает системный администратор Поликарп, компьютерная сеть состоит n компьютеров и m кабелей, которые соединяют некоторые пары компьютеров. Другими словами, компьютерная сеть может быть представлена некоторым неориентированным графом из n вершин и m ребер. Пронумеруем компьютеры целыми числами от 1 до n, пронумеруем кабели целыми числами от 1 до m.
Поликарпу поручили ответственное задание — проверить надежность компьютерной сети его корпорации. Для этого Поликарп решил провести серию из k экспериментов с компьютерной сетью, где i-ый эксперимент заключается в следующем:
- Временно отсоединить кабели с номерами от li до ri, включительно (остальные кабели остаются подсоединенными).
- Посчитать количество компонент связности в графе, который определяет компьютерную сеть в настоящий момент.
- Подсоединить отключенные кабели с номерами от li до ri (то есть восстановить исходную сеть).
Помогите Поликарпу провести все эксперименты и для каждого из них выведите количество компонент связности в графе, который определяет компьютерную сеть во время данного эксперимента. Изолированную вершину нужно считать отдельной компонентой.
Выходные данные
Выведите k чисел, в которых i-ое число обозначает количество компонент связности графа, который определяет компьютерную сеть во время i-го эксперимента.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 5
1 2
5 4
2 3
3 1
3 6
6
1 3
2 5
1 5
5 5
2 4
3 3
|
4
5
6
3
4
2
|