Đảo chiều đường một chiều
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Đề bài
Một thành phố có $N$ giao lộ (đánh số từ $1$ đến $N$) và $M$ con đường một chiều. Bạn muốn đi từ giao lộ $1$ đến giao lộ $N$. Nếu muốn, bạn có thể xin phép đảo chiều một số con đường để đi ngược lại.
Hãy tìm số lượng con đường ít nhất cần phải đảo chiều để có thể đi từ $1$ đến $N$.
Dữ liệu vào
Dòng đầu chứa hai số nguyên $N, M$.
$M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ mô tả con đường một chiều từ $u$ đến $v$.
Dữ liệu ra
In ra số lượng cạnh ít nhất cần đảo chiều để đi từ $1$ đến $N$. Nếu không thể đi được dù có đảo chiều bao nhiêu cạnh đi nữa, in ra -1.
Ví dụ
| Input | Output |
|---|---|
| 5 5 1 2 3 2 3 4 5 4 4 5 |
1 |
| 4 2 1 2 3 4 |
-1 |
Giới hạn
- $1 \le N \le 10^5$
- $0 \le M \le 2 \cdot 10^5$
- $1 \le u, v \le N$
Community Discussion