Định lý Kőnig: Tập phủ đỉnh nhỏ nhất và Tập độc lập lớn nhất trên đồ thị hai phía

Mô tả bài toán

Cho đồ thị hai phía gồm hai tập đỉnh L (gồm các đỉnh {0, 1, …, |L|-1}) và R (gồm các đỉnh {0, 1, …, |R|-1}). Có M cạnh nối giữa một đỉnh thuộc L và một đỉnh thuộc R.

Theo Định lý Kőnig: Trong đồ thị hai phía, kích thước của Cặp ghép cực đại (Maximum Matching) bằng kích thước của Tập phủ đỉnh nhỏ nhất (Minimum Vertex Cover - MVC). Ngoài ra, Tập độc lập lớn nhất (Maximum Independent Set - MIS) chính là phần bù của MVC.

Yêu cầu:

• Tìm kích thước của MVC (ký hiệu K).
• Liệt kê các đỉnh trong MVC của L và R.
• Liệt kê các đỉnh trong MIS của L và R.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên |L|, |R|, M (1 ≤ |L|, |R| ≤ 1000, 0 ≤ M ≤ 10,000).
• M dòng tiếp theo, mỗi dòng chứa hai số nguyên u, v thể hiện cạnh nối giữa đỉnh u ∈ L và v ∈ R (0 ≤ u < |L|, 0 ≤ v < |R|).

Dữ liệu ra

• Dòng 1: In ra số nguyên K là kích thước của Minimum Vertex Cover.
• Dòng 2: Danh sách các đỉnh thuộc L được chọn vào MVC (in số lượng, theo sau là các chỉ số tăng dần).
• Dòng 3: Danh sách các đỉnh thuộc R được chọn vào MVC (in số lượng, theo sau là các chỉ số tăng dần).

*(Lưu ý: Nếu có nhiều MVC cùng kích thước nhỏ nhất, in ra bộ MVC thu được từ thuật toán DFS tìm vết luồng chuẩn của Kőnig: các đỉnh L KHÔNG tới được từ tập L tự do và các đỉnh R ĐẾN ĐƯỢC từ tập L tự do).*

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ả.