Задача №114095. Дорожная реформа
Король Берляндии решил в очередной раз провести дорожную реформу.
Берляндия состоит из \(n\) городов, соединённых \(m\) односторонними дорогами. По каждой из дорог разрешается двигаться только в одну сторону. Двигаться по дороге в противоположную сторону запрещается.
Во время реформы король планирует изменить направление у некоторых дорог так, чтобы существовал путь из города \(1\) в город \(n\), проходящий только по дорогам. Из-за сложностей законодательства король может проводить только операции двух типов.
-
Выбрать некоторый город \(u\). Рассмотрим все города \(v\) такие, что существует дорога между городами \(u\) и \(v\) (направление не важно) и изменим её направление так, чтобы она вела из города \(v\) в город \(u\).
- Выбрать некоторый город \(u\). Рассмотрим все города \(v\) такие, что существует дорога между городами \(u\) и \(v\) (направление не важно) и изменим её направление так, чтобы она вела из города \(u\) в город \(v\).
Выполнение каждой из этих операций крайне затратно, поэтому короля интересует, какое минимальное количество операций ему придётся произвести, чтобы достичь своей цели. Помогите королю, сообщив ему минимальное количество операций, или определите, что король не сможет достичь своей цели ни за какое количество операций.
В первой строке содержатся два целых числа \(n\) и \(m\) (\(2 \leq n \leq 500\,000, 0 \leq m \leq 1\,000\,000\)) — количество городов и дорог в Берляндии, соответственно.
В следующих \(m\) строках содержатся пары целых чисел \(u_i\) и \(v_i\) (\(1 \leq u_i, v_i \leq n, u_i \neq v_i\)), описывающие дорогу между городами \(u_i\) и \(v_i\) направленную из \(u_i\) в \(v_i\). Гарантируется, что между любыми двумя городами есть не более одной дороги (в любом из направлений).
Выведите одно целое число — минимальное количетсво операций, которые потребуется выполнить королю. Если король не сможет достичь своей своей цели ни за какое количество операций выведите \(-1\).
В первом примере в Берляндии нет дорог, поэтому король не сможет сделать так, чтобы из города \(1\) можно было доехать до города \(2\).
Во втором примере изначально из города \(1\) в город \(5\) проехать нельзя, но король может выбрать все дороги, у которых одним из концов является город \(5\) (это дороги \(2-5\) и \(5-4\)) и изменить их направление так, чтобы они вели в сторону города \(5\). После этого из города \(1\) в город \(5\) можно будет проехать по маршруту \(1-3-4-5\).
Тесты к этой задаче состоят из четырёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
2 0
-1
5 6 2 1 1 3 2 3 3 4 2 5 5 4
1