Hành trình của hai robot

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

Trên một đồ thị vô hướng gồm $N$ đỉnh và $M$ cạnh, có hai robot đang đứng ở hai đỉnh phân biệt $S_1$ và $S_2$. Robot $1$ cần đi tới đỉnh $T_1$, robot $2$ cần đi tới đỉnh $T_2$.

Trong mỗi giây, cả hai robot bắt buộc phải đồng thời di chuyển sang một đỉnh kề theo một cạnh. Để tránh va chạm, tại bất kỳ thời điểm nào:

  • Hai robot không được đứng cùng một đỉnh.
  • Hai robot không được đi ngược chiều nhau trên cùng một cạnh trong cùng một giây (tức không được đổi chỗ trực tiếp cho nhau).

Hãy tìm thời gian ngắn nhất để hai robot đồng thời có mặt tại $T_1$ và $T_2$.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N, M$.

Dòng thứ hai chứa bốn số nguyên $S_1, T_1, S_2, T_2$.

$M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ mô tả cạnh vô hướng giữa $u$ và $v$.

Dữ liệu ra

In ra số giây ngắn nhất để hai robot cùng tới đích, hoặc -1 nếu không thể.

Ví dụ
Input Output
4 4
1 4 4 1
1 2
2 4
1 3
3 4
2
3 2
1 3 3 1
1 2
2 3
-1
Giới hạn
  • $2 \le N \le 40$
  • $0 \le M \le N(N-1)/2$
  • $1 \le S_1, T_1, S_2, T_2 \le N$, $S_1 \ne S_2$
Draft saved