Задачи
Обернуть граф
Обернуть граф
Задан ориентированный граф с $n$ вершинами и $m$ ребрами. Вершины графа пронумерованы от $1$ до $n$. Найдите наименьшее количество ребер, которое следует обернуть, чтобы существовал хотя бы один путь от вершины $1$ до вершины $n$.
\InputFile
Первая строка содержит два целых числа $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$.
\OutputFile
Выведите наименьшее количество ребер, которое следует обернуть. Если невозможно получить ни одного пути от $1$ до $n$, выведите $-1$.
\includegraphics{https://static.e-olymp.com/content/a3/a323657425ee743acea3408abb66e49eb10c4678.gif}
Входные данные #1
7 7 1 2 3 2 3 4 7 4 6 2 5 6 7 5
Выходные данные #1
2