Codeforces Round 148 (Div. 1) |
---|
Закончено |
Урпал живет в большом городе. Он назначил свидание своей любимой этим вечером.
Всего в городе 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 ≤ n; a ≠ b).
Следующие m строк содержат по два целых числа ui и vi (1 ≤ ui, vi ≤ n; ui ≠ vi), которые описывают направленную дорогу из перекрестка ui до перекрестка vi. Все дороги во входных данных различны.
В следующей строке записано целое число k (0 ≤ k ≤ 100). Затем идут k строк, содержащих целые числа si и ti (1 ≤ si, ti ≤ n; si ≠ 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
Название |
---|