В непроходимом лесу имеется N полянок и M тропинок между ними. Каждая тропинка соединяет две различные полянки. Две полянки могут быть соединены несколькими тропинками.

На двух разных полянках живут Красная Шапочка и ее бабушка. Домик Красной Шапочки находится на полянке с номером 1, а домик бабушки - на полянке с номером N. Красная Шапочка хорошо ориентируется в лесу и знает, какое минимальное время ей потребуется для прохождения каждой тропинки. Когда Красная Шапочка идет по лесу, она переходит с тропинки на тропинку только на полянках. На каждой полянке есть укрытие, в котором Красная Шапочка может спрятаться на некоторое время.

В этом же лесу живет Волк. Время, за которое Волк пробегает какую-либо тропинку, может отличаться от времени, за которое по ней проходит Красная Шапочка. Кроме того, если Волк пробегает по одной и той же тропинке несколько раз, то каждый раз он может тратить на это разное время.

С края полянки, где живет Красная Шапочка, Волк увидел, что она собирается нести пирожки бабушке и побежал по тропинкам привычного ему пути от дома Красной Шапочки к дому бабушки. Волк начинает бежать от домика Красной Шапочки в тот момент, когда она решила выйти из дома, его путь заканчивается как только он окажется на полянке с домиком бабушки. Ни на одной полянке Волк не задерживается.

Чтобы застать бабушку в целости и сохранности, Красной Шапочке необходимо обогнать Волка. При этом ей нельзя оказаться с Волком на одной тропинке, даже если Волк уже покидает ее, а она только появляется на ней, или наоборот. Чтобы избежать встречи с Волком на полянке, Красная Шапочка использует имеющееся там укрытие. Красной Шапочке нельзя появляться на полянке одновременно с Волком или покидать укрытие на полянке в тот момент, когда на ней появляется Волк. При необходимости Красная Шапочка может идти по тропинке дольше минимально возможного времени, а также выйти из дома позже, чем она исходно решила.

Необходимо написать программу, которая поможет Красной Шапочке добраться к бабушке раньше Волка, если известна последовательность тропинок, по которым побежал Волк.