eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Оранжевий настрій

Оранжевий настрій

Одного разу президент клубу європейського рівня "Надир" оголосив про те, що з наступного сезону голландського тренера, який завоював повагу вболівальників, може змінити менш успішний італієць. Дізнавшись про це, обурені фанати клубу попрямували до палацу президента, щоб учинити помаранчеву (за кольором футболок збірної Голландії) революцію і повернути тренера. Виявилося, що президентська охорона також вболівала за "Надир"... Президент перебуває у палаці, що складається з множини кімнат і коридорів, які їх з'єднують. Дві різні кімнати можуть бути з'єднані не більше, ніж одним коридором. На обох кінцях кожного коридору знаходяться двері. Деякі двері мають засув, який можна замикати або відмикати, перебуваючи всередині кімнати. Замкнений засув блокує доступ до кімнати з відповідного коридору. Через деякі кімнати (входи) до палацу можна потрапити зовні. Спочатку всі двері відкриті. Ваше завдання полягає у тому, щоб визначити, чи може президент вибрати кімнату для укриття від обурених уболівальників так, щоб, стартуючи з цієї кімнати, він міг пройти по коридорах палацу, закрити частину дверей і потім повернутися в своє укриття таким чином, щоб доступ у нього ззовні палацу був закритий. \InputFile Перший рядок вхідного файлу містить три цілих числа \textbf{N}, \textbf{M}, \textbf{P} - кількість кімнат палацу, число коридорів і кількість входів до палацу (\textbf{1} ≤ \textbf{N} ≤ \textbf{10000}, \textbf{0} ≤ \textbf{M} ≤ \textbf{1000000}, \textbf{1} ≤ \textbf{P} ≤ \textbf{N}). Другий рядок містить \textbf{P} чисел - номери кімнат, через які можна потрапити у палац. У наступних \textbf{M} рядках описані коридори палацу. Кожен коридор задається парою цілих чисел від \textbf{1} до \textbf{N} - номерами кімнат, які він з'єднує. Далі в N рядках знаходяться описи кімнат - число \textbf{P_i} - кількість і \textbf{P_i} чисел - номери коридорів, двері у які можна замкнути, перебуваючи у кімнаті (\textbf{0} ≤ \textbf{P_i} ≤ \textbf{100}). Кімнати і коридори пронумеровані цілими числами, починаючи з одиниці, у порядку появи їх у вхідному файлі. \OutputFile У вихідний файл потрібно вивести єдине число - номер кімнати палацу, у якій може сховатися президент. Якщо таких номерів декілька, вивести найменший з них. Якщо сховатися неможливо, вивести фразу "\textbf{Impossible}" (без лапок).
Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
4 3 1
1
1 2
2 3
3 4
0
0
1 2
0
Вихідні дані #1
3