Hành trình chẵn bước
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Đề bài
Cho một đồ thị vô hướng gồm $N$ đỉnh và $M$ cạnh. Một bước di chuyển từ đỉnh này sang đỉnh kề mất $1$ đơn vị thời gian. Bạn được phép đi lại qua các đỉnh hoặc các cạnh nhiều lần.
Hãy tìm độ dài (số cạnh) ngắn nhất của một lộ trình từ đỉnh $S$ đến đỉnh $T$ sao cho tổng số bước đi là một số chẵn.
Dữ liệu vào
Dòng đầu chứa bốn số nguyên $N, M, S, T$.
$M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ biểu thị một cạnh vô hướng giữa $u$ và $v$.
Dữ liệu ra
In ra độ dài ngắn nhất là số chẵn để đi từ $S$ đến $T$. Nếu không tồn tại lộ trình như vậy, in ra -1.
Ví dụ
| Input | Output |
|---|---|
| 4 4 1 4 1 2 2 3 3 4 1 3 |
2 |
| 4 3 1 4 1 2 2 3 3 4 |
-1 |
Giới hạn
- $1 \le N \le 10^5$
- $0 \le M \le 2 \cdot 10^5$
- $1 \le S, T \le N$
Community Discussion