Hành trình chẵn bước

General
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Submissions
Đề 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$
Draft saved