Робокомпанию возглавляет жестокий человек. Его девиз: «Движение или смерть»! Именно этим его продукт и занимается. Рассмотрим поведение робота этой компании. Пусть робот движется по ориентированному графу. Поведение робота на таком графе называется «Три закона робототехники»:

• Закон 1. Робот самоликвидируется, если посетит ранее посещенную вершину графа.
• Закон 2. Робот самоликвидируется, если окажется в ситуации, в которой ему некуда будет идти (иными словами, если робот зайдет в вершину, исходящая степень которой равна нулю).
• Закон 3. Робот движется случайным образом, когда он может двигаться в нескольких направлениях (то есть, когда он достигает вершины, исходящая степень которой больше единицы). Конечно, робот может двигаться только по направленным ребрам графа.

Можете представить робота с таким поведением? Поэтому они очень дешевые и рассчитаны на потребителя, стесненного в средствах. Среди них, конечно, есть пользователь mzry1992. У mzry1992 имеется такой робот и она хочет переместить его из вершины s в вершину t по направленному графу так, чтобы робот не самоликвидировался. К счастью, в каждой вершине девушка может посылать роботу специальные приказ. Специальный приказ показывает роботу нужное направление в тех случаях, когда у робота есть несколько направлений на выбор (во избежание случайного выбора направления робота согласно закону 3). Когда робот дойдет до вершины номер t, mzry1992 немедленно изымает его из графа. Таким образом, девушка всегда найдет способ достичь желаемого результата, при условии, что существует путь из s в t (независимо от того, равна ли исходящая степень вершины t нулю или нет).

Тест 2

Однако отсылать приказы недешево. Поэтому Ваша задача — найти наименьшее количество приказов, которые должна отдать mzry1992 в наихудшем случае. Заметим, что mzry1992 может отдавать приказ роботу в момент движения робота по графу. Обратите внимание на первый пример для лучшего понимания этой части задачи.