Đường đi ngắn nhất giữa hai trạm

General
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Hệ thống tàu điện ngầm gồm $N$ nhà ga đánh số từ $1$ đến $N$ và $M$ tuyến đường hai chiều kết nối trực tiếp giữa các cặp nhà ga. Mỗi tuyến đường mất đúng $1$ phút để di chuyển.

Hãy tìm thời gian ngắn nhất (tính bằng phút) để đi từ nhà ga $S$ đến nhà ga $T$, hoặc cho biết không thể đi tới được.

Dữ liệu vào

Dòng đầu tiên chứa bốn số nguyên $N, M, S, T$ ($1 \le S, T \le N$).

$M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ mô tả một tuyến đường hai chiều nối ga $u$ và ga $v$.

Dữ liệu ra

In ra một số nguyên duy nhất là số phút ngắn nhất để đi từ $S$ đến $T$. Nếu không thể đến $T$, in ra -1.

Ví dụ
Input Output
5 5 1 5
1 2
2 3
3 5
1 4
4 5
2
4 2 1 4
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$
Draft saved