eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 6 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

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

Giriş verilənləri

Первая строка содержит два целых числа 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.

Çıxış verilənləri

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

Nümunə

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