Участники квеста находятся в комнатах, каждый в отдельной, двери закрыты. Некоторые команты соединены между собой коридорами-переходами. Из нескольких комнат есть выход из квеста, но выходы пока тоже закрыты.
В каждой комнате, где находится участник, на стене висит план комнат и соединяющих их коридоров, на изучение которого участникам дается некоторое время. В момент, когда двери откроются, все участники начнут движение, торопясь к ближайшей комнате с выходом.
Как только кто-то из участников квеста доберется до выхода и выйдет, он станет победителем. Возможно, победителей будет несколько, если несколько человек окажутся у выходов (одного и того же или разных - не важно) одновременно. После этого все двери опять закроются, и проигравшие останутся ждать начала новой игры.
В одной из комнат находится Ваш друг, и Вы очень хотите ему помочь победить в этом квесте. Он смог переслать Вам план этого квеста, а также Вам известен номер комнаты, в которой он сейчас находится. Помогите своему другу - подскажите, к какому из выходов ему следует бежать, чтобы минимизировать время. Если таких выходов несколько, укажите минимальный номер. Под номером выхода подразумевается номер комнаты, в которой он находится.
Формат входных данных
В первой строке вводятся три натуральных числа
N,
K, S (1<=N<=100000, 1<=K<=N, 1<=S<=N) — количество комнат, количество выходов и номер комнаты, в которой сейчас Ваш друг, соответственно. Во второй строке через пробел записаны
K различных чисел, обозначающих номера комнат, в которых расположены выходы. В третьей строке идёт число
M (1<=M<=100000) — количество коридоров. В следующих
M строках вводятся пары чисел – номера комнат, соединенных коридром.
По каждому из коридоров можно двигаться в обе стороны. Может существовать более одного коридора между одной и той же парой комнат.
Формат выходных данных
Выведите номер выхода, к которому нужно бежать Вашему другу.
| № | Входные данные | Выходные данные |
|
1
|
3 1 2
2
3
1 2
3 1
2 3
|
2
|
|
2
|
10 2 3
10 8
9
6 7
7 5
5 8
8 1
1 10
10 3
3 4
4 9
9 2
|
10
|