В дремучем лесу есть множество полянок, некоторые из них соединены тропинками, а некоторые нет. Алеша Попович начинает свой путь на полянке A. Он должен зайти к Бабе Яге на полянку B за мечом-кладенцом, после чего направиться на полянку C на бой со Змеем Горынычем. Посчитайте, какое минимальное количество полянок, которое должен посетить Алеша Попович, если он боится посещать поляну C, пока не взял меч.
Все полянки занумерованы натуральными числами, не превышающими 2^31.
В первой строке вводится 3 значения:
- A — номер полянки, где стартует Алеша;
- B — номер полянки, где живет Баба Яга;
- С — номер полянки, где Алешу ждет Змей Горыныч;
В следующей строке вводится N — количество тропинок, которое также не превышает 2^31.
Последующие N строчек имеют вид: start end, где start и end — номера полянок, которые соединены тропинкой. По тропинке можно пройти в любую сторону.
Выведите 1 число — через какое количество полянок пролегает самый короткий маршрут проходящий из A в B, а потом в C, при том, что по пути из A в B поляну C посещать нельзя. Выведите -1, если маршрут, соответствующий условиям не существует.
1 2 3
3
1 5
2 5
2 3
4
1 2 3
2
1 3
3 2
-1