Задачі
Розвернути граф
Розвернути граф
Задано орієнтований граф з n вершин і m ребер. Вершини графа пронумеровані від 1 до n. Знайдіть найменшу кількість ребер, які варто розвернути, щоб існував хоча б один шлях від вершини 1 до вершини n.
Вхідні дані
Перший рядок містить два цілих числа n і m\:(1 \le n, m \le 2 \cdot 10^6) — кількість вершин і ребер. i-ий рядок з наступних m рядків містить два цілих числа x_i і y_i\:(1 \le x_i, y_i \le n), що означає, що i-е орієнтоване ребро йде від вершини x_i до вершини y_i
Вихідні дані
Виведіть найменшу кількість ребер, яку слід розвернути. Якщо неможливо отримати жодного шляху від 1 до n, виведіть -1.
Приклад
Вхідні дані #1
7 7 1 2 3 2 3 4 7 4 6 2 5 6 7 5
Вихідні дані #1
2