Розвернути граф

Задано орієнтований граф з $n$ вершинами та $m$ ребрами, вершини якого пронумеровані від $1$ до $n$. Знайдіть найменшу кількість ребер, які слід обернути, щоб існував хоча б один шлях із вершини $1$ до вершини $n$.

Вхідні дані

Перший рядок містить два цілих числа $n$ та $m(1\le n,m\le 2\cdot 10^6)$ — кількість вершин та ребер у графі. Кожний з наступних $m$ рядків містить два цілих числа $x_i$ та $y_i(1\le x_i,y_i\le n)$, що означають, що $i$-те орієнтоване ребро йде з вершини $x_i$ у вершину $y_i$.

Вихідні дані

Виведіть мінімальну кількість ребер, які слід обернути. Якщо неможливо отримати шлях із вершини $1$ до вершини $n$, виведіть $-1$.

Приклади