D. Сахир и детский сад
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Сахир работает в детском саду. Всего в саду n детей и m различных игрушек. Чтобы поиграть с игрушками, дети должны следовать определенному протоколу:

  • У каждого ребенка есть набор любимых игрушек. Он запрашивает эти игрушки по одной в различные моменты времени. Ребенок начинает играть, только когда у него окажутся все игрушки из любимого набора.
  • Если ребенок начал играть, то рано или поздно он отдаст все игрушки обратно. Никто не будет держать игрушки вечно.
  • Дети запрашивают игрушки в различные моменты времени, никакие два ребенка не запрашивают игрушки одновременно.
  • Если ребенку дали запрашиваемую игрушку, то он не отдаст ее, пока не закончит играть со своим любимым набором.
  • Если ребенку не дали запрашиваемую игрушку, то он будет ждать, пока ее ему дадут. Он не может запросить другую игрушку, пока ждет. То есть, каждый ребенок в каждый момент времени ждет не более одной игрушки.
  • Если два ребенка ждут одну и ту же игрушку, то сначала ее получит тот, кто запросил ее раньше.

Дети не любят играть друг с другом, поэтому они никогда не делятся игрушками. Когда ребенок запрашивает игрушку, то решение дать ему ее или нет зависит от того, свободна игрушка, или нет. Если игрушка свободна, Сахир даст ее ребенку. Иначе ребенок будет ждать ее и не сможет запрашивать другие игрушки, пока ждет.

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

У вас есть сценарий, в котором все дети запрашивают все игрушки из их любимых наборов, кроме одного ребенка x, который запросит еще одну игрушку. Сценарий таков, что после выполнения запросов из сценария некоторые дети начнут играть, а некоторые будут ждать последнюю игрушку, но никто не будет плакать. Если ребенок x будет ждать какую-то игрушку, то он сделает свой оставшийся запрос после ее получения. Иначе, он сразу же запросит ее. Когда ребенок x это сделает, сколько детей начнут плакать?

Вам дан сценарий и q независимых запросов. Каждый запрос будет иметь форму x y, что означает, что оставшийся запрос ребенка x — это игрушка y. Ваша задача — помочь Сахиру определить размер максимальной плачущей группы детей после того, как ребенок x сделает свой последний запрос.

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

Первая строка содержит четыре целых числа n, m, k, q (1 ≤ n, m, k, q ≤ 105) — количество детей, игрушек, запросов детей в сценарии и вариантов последнего запроса.

Каждая из следующих k строк содержит по два целых числа a, b (1 ≤ a ≤ n, 1 ≤ b ≤ m), означающих, что в сценарии ребенок a запрашивает игрушку b. Запросы даны в порядке их появления.

Каждая из следующих q строк содержит по два целых числа x и y (1 ≤ x ≤ n, 1 ≤ y ≤ m) — варианты последнего запроса (ребенок x запросит игрушку y как только сможет).

Гарантируется, что все запросы в сценарии удовлетворяют протоколу, и никто не плачет после выполнения запросов из сценария. Все запросы в сценарии различны, и никакой вариант последнего запроса не совпадает с запросами в сценарии.

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

Для каждого запроса выведите на отдельной строке число детей, которые начнут плакать после того, как ребенок x сделает свой последний запрос (игрушку y). Заметьте, что все варианты последнего запроса независимы.

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

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

Во втором примере после исполнения сценария у ребенка номер i будет находиться игрушка i для 1 ≤ i ≤ 4. Дети 1 и 3 уже собрали свой любимый набор. После того, как они закончат играть, игрушка 3 освободится, а игрушку 1 отдадут ребенку 2, и он соберет любимый набор. После того, как он закончит играть, игрушки 1 и 2 освободятся, и ребенок 5 возьмет игрушку 1. Итак:

  • В первом варианте ребенок 5 возьмет игрушку 3, и когда он закончит играть, сможет играть ребенок 4.
  • Во втором варианте ребенок 5 запросит игрушку 4, которая находится у ребенка 4. В то же время ребенок 4 ждет игрушку 1, которая сейчас находится у ребенка 5. Никто из них не сможет начать играть, и они оба заплачут.