Кордон
В одной из звездных систем Галактической Республики произошло дерзкое ограбление банка "13-е Общество межгалактического кредита", из которого было похищено несколько миллиардов буказоидов. Оказалось, что Армия Республики в данном секторе имеет ограниченные силы и не в состоянии блокировать все возможные пути бегства грабителей, поэтому встала задача о минимизации числа кордонов.
Звездные системы соединяются с помощью транспортных коридоров. Один армейский кордон может надежно блокировать только один транспортный коридор. Известно, что грабители еще не успели покинуть ограбленную звездную систему. Кроме этого известно множество систем, в которых грабители могут укрыться. Задача армии состоит в том, чтобы разместить минимальное количество кордонов таким образом, чтобы грабители не могли попасть ни в одну из этих систем.
Первым числорм в потоке входных данных задается общее число N всех звездных систем в галактике (2 ≤ N ≤ 1000). Мы будем предполагать, что все звездные системы пронумерованы от 1 до N. Система, в которой произошло ограбление, имеет номер 1. Далее вводится целое число H, обозначающее количество систем, в которых грабители могут укрыться. Затем перечисляются H целых чисел si (1 ≤ i ≤ H), задающее неповторяющиеся номера звездных систем (2 ≤ si ≤ N) укрытия. После этого вводится число T транспортных коридоров в галактике. Каждый транспортный коридор j (1 ≤ j ≤ T) задается парой целых чисел fj, tj (fj ≠ tj) – номеров звёздных систем, которые он соединяет. Транспортный коридор работает только в одном направлении от системы fj к системе tj. Любая пара звёздных систем может быть соединена максимум одним транспортным коридором. Транспортная сеть такова, что от системы 1 ко всем система sj существует путь, проходящий по транспортным коридорам.
Напечатайте сначала целое число M – минимальное количество необходимых кордонов. Затем напечатайте M транспортных коридоров, которые должны быть заблокированы. Каждый транспортный коридор должен быть выведен как пара целых чисел fk, tk.
5 1 5 6 1 2 1 3 2 3 2 4 3 4 4 5
1 4 5