Kiểm tra mạng rồi tìm đường

Bối cảnh và bài toán

Một mạng vô hướng được kiểm tra theo hai bước: trước tiên đếm số thành phần liên thông; nếu mạng đã liên thông mới cần tìm số cạnh ít nhất từ s tới t.

Yêu cầu

Nếu mạng có k>1 component, in 'DISCONNECTED k'. Nếu liên thông, in 'CONNECTED d' với d là khoảng cách BFS từ s tới t.

Input

Dòng đầu n, m, s, t; tiếp theo m cạnh vô hướng.

Output

Theo mô tả yêu cầu.

Ràng buộc

• 2 <= n <= 2*10^5
• 0 <= m <= 2*10^5 ## Chấm điểm | Subtask | Điểm | Điều kiện | Official tests | |---|---:|---|---| | S1 | 40 | n <= 200, m <= 500 (nếu có m) | 01–08 | | S2 | 60 | Không có ràng buộc bổ sung | 09–20 |

Ví dụ 1

Input

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

Output

CONNECTED 4

Giải thích. Chỉ khi mạng liên thông mới chuyển sang yêu cầu khoảng cách BFS.

Ví dụ 2

Input

5 2 1 5
1 2
4 5

Output

DISCONNECTED 3

Giải thích. Chỉ khi mạng liên thông mới chuyển sang yêu cầu khoảng cách BFS.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.