e-olymp
favorite Saytın davamlılığını təmin etmək üçün sizin köməyinizə ehtiyacımız vardır, ətrafli məlumat üçün bannerə klikləyin
Yarışlar

0-1 BFS

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

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

Входные данные

Первая строка содержит два целых числа n и m (1n, m2 * 106) - количество вершин и ребер. i-ая строка из следующих m строк содержит два целых числа xi и yi (1xi, yin), означающих что i-ое ориентированное ребро идет от вершины xi до вершины yi.

Выходные данные

Выведите наименьшее количество ребер, которое следует обернуть. Если невозможно получить ни одного пути от 1 до n, выведите -1.

prb10048.gif

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
7 7
1 2
3 2
3 4
7 4
6 2
5 6
7 5
Çıxış verilənləri #1
2