Задан ориентированный граф с n вершинами и m ребрами. Вершины графа пронумерованы от 1 до n. Найдите наименьшее количество ребер, которое следует обернуть, чтобы существовал хотя бы один путь от вершины 1 до вершины n.
Первая строка содержит два целых числа n и m(1≤n,m≤2⋅106) — количество вершин и ребер. i-ая строка из следующих m строк содержит два целых числа xi и yi(1≤xi,yi≤n), означающих что i-ое ориентированное ребро идет от вершины xi до вершины yi.
Выведите наименьшее количество ребер, которое следует обернуть. Если невозможно получить ни одного пути от 1 до n, выведите −1.