D. Компоненты связности
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В уже известной нам некоторой большой корпорации, в которой работает системный администратор Поликарп, компьютерная сеть состоит n компьютеров и m кабелей, которые соединяют некоторые пары компьютеров. Другими словами, компьютерная сеть может быть представлена некоторым неориентированным графом из n вершин и m ребер. Пронумеруем компьютеры целыми числами от 1 до n, пронумеруем кабели целыми числами от 1 до m.

Поликарпу поручили ответственное задание — проверить надежность компьютерной сети его корпорации. Для этого Поликарп решил провести серию из k экспериментов с компьютерной сетью, где i-ый эксперимент заключается в следующем:

  1. Временно отсоединить кабели с номерами от li до ri, включительно (остальные кабели остаются подсоединенными).
  2. Посчитать количество компонент связности в графе, который определяет компьютерную сеть в настоящий момент.
  3. Подсоединить отключенные кабели с номерами от li до ri (то есть восстановить исходную сеть).

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

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

В первой строке через пробел заданы два целых числа n, m (2 ≤ n ≤ 500; 1 ≤ m ≤ 104) — количество компьютеров и количество кабелей соответственно.

Далее в m строках задано описание кабелей. В i-ой строке через пробел задана пара целых чисел xi, yi (1 ≤ xi, yi ≤ n; xi ≠ yi) — номера компьютеров, которые соединяет i-ый кабель. Обратите внимание, что пара компьютеров может быть соединена несколькими кабелями.

В следующей строке задано единственное целое число k (1 ≤ k ≤ 2·104) — количество экспериментов. Далее в k строках задано описание экспериментов. В i-ой строке через пробелы заданы числа li, ri (1 ≤ li ≤ ri ≤ m) — номера кабелей, которые Поликарп отсоединяет во время i-го эксперимента.

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

Выведите k чисел, в которых i-ое число обозначает количество компонент связности графа, который определяет компьютерную сеть во время i-го эксперимента.

Примеры
Входные данные
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