D. Управляем роботом
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

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

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

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

Тест 2

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

Входные данные

Первая строка содержит два целых числа n (1 ≤ n ≤ 106) — количество вершин графа, и m (1 ≤ m ≤ 106) — количество ребер. Затем следует m строк, в каждой строке записано два целых числа, ui и vi (1 ≤ ui, vi ≤ n; vi ≠ ui), эти целые числа обозначают направленное ребро, проходящее из вершины ui в вершину vi. В последней строке записано два целых числа, s и t (1 ≤ s, t ≤ n).

Гарантируется, что граф не содержит петель и кратных ребер.

Выходные данные

Если выполнить поставленную цель возможно, выведите требуемое минимальное количество приказов в худшем случае. Иначе выведите -1.

Примеры
Входные данные
4 6
1 2
2 1
1 3
3 1
2 4
3 4
1 4
Выходные данные
1
Входные данные
4 5
1 2
2 1
1 3
2 4
3 4
1 4
Выходные данные
1
Примечание

Рассмотрим первый пример. Изначально робот находится в вершине номер 1. Таким образом, на первом шагу робот может пойти в вершину 2 или 3. В зависимости от выбора робота, mzry1992 должна отдать приказ роботу. Приказ направляет его в вершину 4. Если mzry1992 не отдает приказа роботу на вершине 2 или 3, то робот может выбрать «плохое» исходящее ребро (вернуться в вершину 1) согласно закону № 3. Таким образом, ответ — один.