Cheating
Дизайн и Анализ на Алгоритми, 2011
Time Limit: 0.1s, Memory Limit: 64MiB
Ели най-сетне откри ключа към успеха на изпита по ДАА: преписване. За съжаление то не винаги е безопасно и понякога студентите биват късани на изпита, а дори и дисциплинарно наказвани. Ето защо Ели иска да препише по възможно най-безопасния начин.

Преписването е малко или много доста праволинеен процес. Винаги има хора, които могат да решат задачите и такива, които искат да препишат (като нея). Знаещите, след като измислят решенията, ги предават на съседите си, които от своя страна ги предават на своите съседи, и така нататък, докато отговорите стигнат до всички, искащи да препишат (в частност до Ели). Понякога подсказването е сравнително безопасно (ако студентите са един до друг), а понякога не е. Ели е бинарно момиче, затова се ограничава само до тези две нива на безопасност.

Тя знае къде са разположени нейните колеги и също така знае единствения човек, който може да реши задачите. Освен това тя знае и двойките хора, които могат да си подсказват безопасно и тези, които могат, но с риск да бъдат хванати. Ели се чуди колко на брой „опасни” подсказвания трябва да бъдат направени за да стигнат отговорите до нея в най-безопасния вариант (ако студентите си подсказват оптимално).
Вход
На първия ред на стандартния вход ще бъдат зададени числата N, М и K – съответно броят студенти на изпита, броят двойки, които могат да си говорят безопасно и броят двойки, които могат да си подсказват, но с риск да бъдат хванати. Следват М реда, съдържащи индексите на двойките студенти, които могат да си говорят безопасно. Входът завършва с К реда, на всеки от които има индексите на двама студенти, които могат да си подсказват с опасност да ги хванат.
Всички индекси на студенти са между 1 и N, включително. Ели е с индекс 1, а студентът, който знае как се решават задачите, е с индекс N.
Изход
На стандартния изход изпечатайте едно единствено число – минималния брой опасни подсказвания, които трябва да бъдат извършени за да стигнат решенията до Ели. Ако решенията не могат да стигнат до нея, вместо това изпечатайте -1.
Ограничения
  • 1 ≤ N ≤ 10,000
  • 1 ≤ M + K ≤ 100,000
Примерен Вход Примерен Изход
9 5 6 1 4 2 4 5 6 8 9 5 7 9 6 1 3 1 2 5 8 2 5 3 5 2
3 0 1 2 1 -1
В първия пример Ели може да използва или 9 -> 8 -> 5 -> 2 -> 4 -> 1 или 9 -> 6 -> 5 -> 2 -> 4 -> 1, като и двете вериги съдържат по две двойки студенти, които биха могли да бъдат хванати. Забележете, че 9 -> 6 -> 5 -> 3 -> 1 съдържа по-малко на брой студенти, но три опасни ребра. Във втория пример няма връзка между Ели и студента с решенията, затова отговорът е -1.
Мрън!