Обернуть граф

Задан ориентированный граф с $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$.

Примеры