В стране имеется ровно n городов, пронумерованные натуральными числами от 1 до n. В каждом городе находится аэропорт.
Также в стране имеется единственная авиакомпания, которая совершает m рейсов. К сожалению, чтобы воспользоваться ими, вам требуется быть постоянным клиентом этой компании, а именно, вы имеете возможность пользоваться рейсом номер i из города ai в город bi только в том случае, если вы уже совершили не менее di перелетов с использованием рейсов авиакомпании.
Обратите внимание, что рейс с номером i летит именно из города ai в город bi. Им нельзя воспользоваться, чтобы прилететь из города bi в город ai. Интересная особенность услуг, предоставляемых авиакомпанией, заключается в том, что бывают развлекательные полеты с прекрасным видом на небо, которые начинаются и заканчиваются в одном и том же городе.
Вам необходимо попасть из города 1 в город n. К сожалению, до этого вы никогда не путешествовали самолетом. Какое минимальное число перелетов вам потребуется, чтобы осуществить это путешествие?
Обратите внимание, что одним и тем же рейсом можно летать несколько раз.
Выходные данные
Выведите «Impossible» (без кавычек), если невозможно добраться из города 1 в город n услугами данной авиакомпании.
Если же хотя бы один способ существует, выведите одно число — минимальное количество авиаперелетов, которое вам потребуется сделать, чтобы добраться до пункта назначения.