Kiểm Tra Độ Liên Thông Đỉnh Bằng Luồng Cực Đại (Vertex Connectivity)

Mô tả bài toán

Cho một đồ thị vô hướng G = (V, E) gồm N đỉnh và M cạnh. Cho trước hai đỉnh phân biệt S và T không có cạnh nối trực tiếp giữa chúng.

Theo định lý Menger, số lượng lớn nhất các đường đi độc lập về đỉnh (internally vertex-disjoint paths - hai đường đi chỉ chung nhau hai đầu mút S và T, không có đỉnh trung gian nào chung) bằng số lượng đỉnh tối thiểu cần xóa để ngắt hoàn toàn kết nối giữa S và T.

Hãy tìm số lượng tối đa các đường đi độc lập về đỉnh nối giữa S và T.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• Thời gian chạy tối đa: 1000ms.
• Giới hạn bộ nhớ: 256MB.
• Dữ liệu đầu vào tuân thủ đúng định dạng và miền giá trị được mô tả.