Жахливий список#6834

Жахливий список

1 секунда

128 мегабайтів

Дуже легка

Настав час $7$ -го Північного З'їзду Попкорну, і цього року у менеджера Яна з'явилася блискуча ідея. На додаток до традиційної програми кінопоказу, було вирішено облаштувати незвичайну кімнату, в якій невелика група людей може переглянути випадковий фільм з великої колекції, насолоджуючись попкорном і мартіні.

Але як виявилося, деякі відвідувачі були занадто розчаровані, оскільки їм довелося дивитися такі фільми як Привид Марса - це змушувало людей рвати на собі волосся у відчаї та жаху.

Щоб уникнути цієї проблеми на наступному з'їзді, Ян придумав рішення, але Ви повинні допомогти його реалізувати. Коли група людей входить у незвичайну кімнату, вони вводять список фільмів на комп'ютері. Це буде жахливий список, що складається з фільмів, які ніхто з групи не бажає дивитися. Звісно ж, список варіюється від групи до групи.

У Вас є доступ до бази порівнянь Жахливих Фільмів, яка вказує які фільми безпосередньо подібні до яких. Вважайте, що фільми, подібні до поганих, самі погані. Визначимо індекс Жахливості $H I$ наступним чином:

$H I = 0$ HI = 0, якщо фільм включений у жахливий список. Це скасовує інші визначення.

$H I = q + 1$ HI = q + 1, якщо найгірший безпосередньо подібний фільм має $H I = q$ HI = q,

$H I = + \infty$ HI = +\infty, якщо фільм не є подібним до жахливого.

Вхідні дані

Перший рядок містить три натуральних числа $n$ , $h$ , $l$ ( $1 \leq h < n \leq 1000$ 1 \le h < n \le 1000, $0 \leq l \leq 10000$ 0 \le l \le 10000), де $n$ - кількість фільмів (представлених $I D$ від $0$ до $n - 1$ n - 1), $h$ - кількість фільмів у жахливому списку, а $l$ - кількість схожостей у базі даних.

Другий рядок містить $h$ унікальних цілих $x_{i}$ x_i ( $0 \leq x_{i} < n$ 0 \le x_i < n), що вказують на $I D$ фільмів у жахливому списку.

Кожен з наступних $l$ рядків містить два цілі числа $a_{i}$ a_i, $b_{i}$ b_i ( $0 \leq a_{i} < b_{i} < n$ 0 \le a_i < b_i < n), що вказують на те, що фільм з $I D$ $a_{i}$ a_i подібний до фільму з $I D$ $b_{i}$ b_i (і навпаки).

Вихідні дані

Виведіть $I D$ найкращого фільму колекції (з найвищим індексом жахливості). Якщо таких фільмів кілька, то виведіть фільм з найменшим $I D$ .

Приклади

Приклад 1

Приклад 2