E. Встретить Ее
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Урпал живет в большом городе. Он назначил свидание своей любимой этим вечером.

Всего в городе n перекрестков, пронумерованных от 1 до n. Перекрестки соединены m направленными улицами, все улицы имеют одинаковую длину. Урпал живет на перекрестке a, а свидание назначено в ресторане на перекрестке b. Он хочет добраться до перекрестка b на общественном транспорте. Всего есть k автобусных компаний. В начале каждой секунды автобус из i-ой компании выбирает случайный наикратчайший путь между перекрестком si и перекрестком ti и проезжает по этому пути. Возможна такая ситуация, когда от перекрестка si до перекрестка ti не существует никакого пути. В этом случае ни один автобус не отправится из si до ti. Если автобус проезжает перекресток, на котором стоит Урпал, то юноша может сесть на этот автобус. Также он может сойти с автобуса на любом перекрестке на пути.

Урпал хочет знать, возможно ли добраться до свидания на общественном транспорте за конечное время (время его поездки — это сумма длин дорог, которые он проехал) и на какое наименьшее количество автобусов ему придется сесть в наихудшем случае.

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

Обратите внимание, что Урпалу неизвестна скорость автобусов.

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

Первая строка входных данных содержит целые числа n, m, a, b (2 ≤ n ≤ 100; 0 ≤ m ≤ n·(n - 1); 1 ≤ a, b ≤ na ≠ b).

Следующие m строк содержат по два целых числа ui и vi (1 ≤ ui, vi ≤ nui ≠ vi), которые описывают направленную дорогу из перекрестка ui до перекрестка vi. Все дороги во входных данных различны.

В следующей строке записано целое число k (0 ≤ k ≤ 100). Затем идут k строк, содержащих целые числа si и ti (1 ≤ si, ti ≤ nsi ≠ ti), означающие, что есть автобусный путь от si до ti. Обратите внимание, что между перекрестками si и ti может не существовать пути, данная ситуация описана в условии задачи.

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

В единственной строке выходных данных выведите наименьшее количество автобусов, на которые Урпал должен сесть по пути на свидание в наихудшем случае. Если в нахудшем случае пункт назначения достичь невозможно, выведите -1.

Примеры
Входные данные
7 8 1 7
1 2
1 3
2 4
3 4
4 6
4 5
6 7
5 7
3
2 7
1 4
5 7
Выходные данные
2
Входные данные
4 4 1 2
1 2
1 3
2 4
3 4
1
1 4
Выходные данные
-1