В долине древнего леса раскинулось королевство Велесград, охваченное шепотом старины и тайнами дорог. Два заклятых врага отправились в путешествие: Водяной Вит и Ведун Пит — представители враждебных кланов — нашли легенду о ценной реликвии, спрятанной где-то в лесу. Они спешат к сокровищу по тропинкам, соединяющим поляны леса. Но проблема в том, что не все поляны соединены тропами, древний лес строго бережет свои тайны, и каждого, кто свернет с тропы, ждет неминуемая гибель. Зато тому, кто не сворачивает с тропы, лес всегда помогает - как только путник делает первый шаг по тропе, он сразу оказывается на той поляне, куда эта тропа ведет.
Чтобы обогнать соперника и завладеть реликвией, нашим героям непременно нужно как можно быстрей добраться до поляны. У каждого из них есть карта древнего леса, и они, конечно же, ей воспользуются..
Зная, какие тропы связывают какие полняны и где сейчас находятся Водяной и Ведун, определите, кто успеет первым.
Входные данные
В первой строке входного файла четыре числа: N, S, V1, V2 (1 <= N <= 1000; 1 <= S, V1, V2 <= N), где N - общее количество полян в лесу, S - номер поляны, на которой зарыта древняя реликвия, V1, V2 - номера полян, на которых сейчас стоят Вит и Пит соответственно
В следующих N строках по N чисел - 1 или 0. 0 стоящий в I-ой строке на J-ом месте означает отсутствие тропы из I-ой поляны в J-ую, а 1 - наличие такой тропы. Все тропы могут использоваться для передвижения между полянам в обе стороны.
Выходные данные
Вывести Vit, если Вит успеет первым и заберет реликвию. Вывести Pit, если Пит доберется до поляны первым и завладеет сокровищем. Если они одновременно достигнут поляны, то исход их битвы неизвестен, т.к. ни у одного, ни у другого в лесу нет поддержки родной стихии; в этом случае выведите fifty-fifty. Если же ни один из них не дойдет до заветной поляны, а оба будут вечно бродить по древнему лесу, выведите infinity
| № | Входные данные | Выходные данные |
|
1
|
4 1 4 3
0 1 0 1
1 0 1 0
0 1 0 0
1 0 0 0
|
Vit
|
|
2
|
3 1 2 3
0 0 1
0 0 0
1 0 0
|
Pit
|