Alice bị mắc kẹt trong mê cung Wonderland và đang bị Nữ hoàng Cơ cùng người truyền lệnh của bà truy đuổi! Mê cung gồm \(J\) giao lộ được đánh số từ \(1\) đến \(J\), nối với nhau bởi \(C\) hành lang hai chiều.

Alice và Nữ hoàng Cơ luân phiên di chuyển; cả hai luôn biết vị trí của người kia. Trong một lượt, mỗi người có thể đứng yên tại giao lộ hiện tại hoặc đi đến một giao lộ khác được nối với nó bằng hành lang.

Tuy nhiên, người truyền lệnh luôn công bố trước nước đi tiếp theo của Nữ hoàng. Điều đó có nghĩa là trước khi bất kỳ ai di chuyển, ông công bố nước đi đầu tiên của Nữ hoàng. Sau đó Alice đi trước. Mỗi khi Nữ hoàng đi, bà phải tuân theo thông báo trước đó, rồi quyết định nước đi kế tiếp để người truyền lệnh công bố. Alice nghe được mọi thông báo, nên luôn biết nước đi tiếp theo của Nữ hoàng trước khi chọn nước đi của mình.

Nếu Alice và Nữ hoàng ở cùng một giao lộ sau khi một trong hai người di chuyển, Alice bị bắt. Nếu không, cuộc truy đuổi tiếp tục. Sau tổng cộng \(10^9\) nước đi, một nửa của Alice và một nửa của Nữ hoàng, nếu họ vẫn không ở cùng giao lộ thì Nữ hoàng sẽ bỏ cuộc và Alice được an toàn.

Alice chọn nước đi tối ưu để trốn thoát. Nếu không thể thoát, cô chọn cách tối đa hóa tổng số nước đi trước khi bị bắt. Nữ hoàng chọn tối ưu để bắt Alice trong ít nước đi nhất có thể.

Cho sơ đồ mê cung và vị trí ban đầu của Nữ hoàng lẫn Alice, hãy xác định Alice có bị bắt hay không và, nếu có, sau bao nhiêu nước đi.

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Sau đó là \(T\) bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa bốn số nguyên \(J,C,A,Q\): số giao lộ, số hành lang, giao lộ ban đầu của Alice và giao lộ ban đầu của Nữ hoàng.

Tiếp theo là \(C\) dòng. Dòng thứ \(i\) chứa hai số nguyên \(U_i,V_i\), cho biết hành lang thứ \(i\) nối hai chiều hai giao lộ \(U_i\) và \(V_i\).

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ \(1\)). Nếu Alice có thể tránh bị bắt trong tổng cộng \(10^9\) nước đi, \(y\) là SAFE. Nếu không, \(y\) là tổng số nước đi của cả Alice và Nữ hoàng cho đến khi Nữ hoàng bắt được Alice.

Ràng buộc

• \(1\le T\le100\).
• \(1\le A\le J\).
• \(1\le Q\le J\).
• \(A\ne Q\).
• \(1\le U_i<V_i\le J\) với mọi \(i\).
• \((U_i,V_i)\ne(U_j,V_j)\) với mọi \(i\ne j\).

Phân nhóm

• Test Set 1 (phán quyết hiển thị): \(2\le J\le30\) và \(1\le C\le60\).
• Test Set 2 (phán quyết ẩn): \(2\le J\le10^5\) và \(1\le C\le2\times10^5\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

4
5 5 5 1
1 2
1 3
2 4
3 4
4 5
5 5 5 2
1 2
1 3
2 4
3 4
4 5
3 1 2 3
1 3
2 1 1 2
1 2

Case #1: SAFE
Case #2: 4
Case #3: SAFE
Case #4: 2

Nguồn

Google Code Jam 2022, Chung kết thế giới, bài Wonderland Chase.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.