E. Тимофей и братья наши меньшие
ограничение по времени на тест
7 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

После празднования дня рождения Тимофей пошел на свою любимую березовую аллею, чтобы покормить своих любимых птиц — ворон. Вороны уже привыкли к маленькому Тимофею, поскольку он очень добрый и заботливый мальчик — постоянно подкармливает своих любимцев.

Как известно, на каждой березе живет ровно одно семейство ворон. Березы в аллее стоят в ряд и пронумерованы от 1 до n. Также известно, что некоторые семейства дружат между собой. По некоторым причинам одно семейство может дружить с другим, только если они живут на достаточно близком расстоянии, а именно, между любыми двумя дружащими семействами должна быть не более чем k - 1 береза. Более формально, семейство, живущее на дереве u, может дружить с семейством, живущим на дереве v, только если |u - v| ≤ k.

Одно из проявлений дружбы заключается в том, что если некоторое семейство узнает, что Тимофей где-то кормит ворон, то оно немедленно сообщит об этом всем семействам, с которыми оно дружит. Таким образом, после того, как Тимофей начнет кормить ворон около некоторой березы, к месту кормежки слетятся все семейства, которые дружат с семейством, живущим на этой березе, непосредственно или через цепочку нескольких дружественных отношений. Разумеется, обитатели данной березы тоже слетятся.

Сегодня Тимофей пришел на аллею, и обнаружил, что все семейства, живущие на березах с номерами, строго меньшими l или строго большими r, куда-то улетели. Таким образом, передача информации о кормежке через них невозможна. Кроме того, кормить их также не нужно. Помогите Тимофею узнать, возле какого минимального числа берез Тимофею необходимо покормить ворон, чтобы все оставшиеся семейства узнали о кормежке. Вам дано несколько возможных ситуаций, определяемых числами l и r, и требуется посчитать ответ для каждой из них.

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

В первой строке входных данных дается два целых числа n и k (1 ≤ n ≤ 105, 1 ≤ k ≤ 5), где n — количество берез, k — максимально допустимое расстояние между дружащими семействами.

В следующей строке входных данных дается одно целое число m (0 ≤ m ≤ n·k) — количество дружащих пар семейств.

В каждой из следующих m строк находятся два целых числа u и v (1 ≤ u, v ≤ 105), означающих, что семейства, живущие на березах u и v, дружат между собой. Гарантируется, что u ≠ v и |u - v| ≤ k. Все пары дружащих семейств различны.

В следующей строке находится одно целое число q (1 ≤ q ≤ 105) — количество ситуаций, для которых нужно узнать ответ.

В каждой из следующих q строк находятся два целых числа l и r (1 ≤ l ≤ r ≤ 105), означающих, что в этой ситуации улетели все семейства с такими номерами x, что либо x < l, либо x > r.

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

Выведите q строк: в i-той строке должно быть одно число — ответ на i-ю ситуацию.

Пример
Входные данные
5 3
3
1 3
2 3
4 5
5
1 1
1 2
2 3
1 3
1 5
Выходные данные
1
2
1
1
2
Примечание

В первом примере дружат пары семейств (1, 3), (2, 3) и (4, 5).

  • В первой ситуации осталось только первое семейство, поэтому ответ 1.
  • Во второй ситуации остались первые два семейства, при этом они не дружат непосредственно, а значит ответ 2.
  • В третьей ситуации семейства 2 и 3 дружат, поэтому достаточно покормить любое из них, ответ 1.
  • В четвертой ситуации можно покормить, например, первое семейство, от него о кормежке узнает третье, а он него — второе. Ответ 1.
  • В пятой ситуации достаточно покормить первое и пятое семейства, ответ 2.