Волшебник Зейн хочет показать публике фокус с переставлением стаканов.
Есть n стаканов, пронумерованных от 1 до n, расположенных вдоль оси x на столе, на котором имеется m отверстий. Более точно, стакан номер i стоит на столе на позиции x = i.
Игральная кость изначально находится в позиции x = 1. Зейн запутает аудиторию, меняя пару стаканов местами ровно k раз, i-ми по порядку переставляя стаканы на позициях x = ui и x = vi. Если в любой момент времени кость оказывается в позиции, где есть отверстие в столе, она падает в него, и остается на месте до конца фокуса.
Не забудьте, что Зейн волшебник. Поэтому, когда он меняет местами два стакана, он не двигает их по столу, а телепортирует стаканы (вместе с костью, если она внутри какого-то из них) на необходимые позиции. Поэтому, например, при переставлении местами стаканов на местах x = 4 и x = 6, они не окажутся на позиции x = 5 ни в какой момент операции.
Щенок Зейна Инзейн озадачен. Зейн отошел, и Инзейн не может найти свою любимою игральную кость, и будет очень утомительно пытаться открыть все стаканы. Инзейн знает, что сообщество Codeforces уже успешно помогло Зейну, поэтому просит помочь ему тоже. Помогите Инзейну определить финальную позицию кости.
Первая строка содержит три целых числа n, m и k (2 ≤ n ≤ 106, 1 ≤ m ≤ n, 1 ≤ k ≤ 3·105) — количество стаканов, количество отверстий и количество операций переставления, соответственно.
Вторая строка содержит m различных целых чисел h1, h2, ..., hm (1 ≤ hi ≤ n) — координаты вдоль оси x отверстий на столе.
Каждая из следующих k строк содержит два целых числа ui и vi (1 ≤ ui, vi ≤ n, ui ≠ vi) — позиции, стаканы на которых нужно переставить.
Вывеедите одно целое число — финальную позиции кости вдоль оси x.
7 3 4
3 4 6
1 2
2 5
5 7
7 1
1
5 1 2
2
1 2
2 4
2
В первом примере после каждой из операций кость оказывается на позициях x = 2, x = 5, x = 7, и x = 1, соответственно.
Во втором примере после первой операции кость окажется в позиции x = 2 и упадет в отверстие.
| Codeforces Round 408 (Div. 2) |
|---|
| Закончено |
