SỬA ĐƯỜNG

 Một hệ thống giao thông gồm N nút, M đường hai chiều nối các cặp nút (N≤500, M≤20000). Giữa hai nút bất kì có không quá 1 đường nối. Hệ thống bảo đảm sự đi lại giũa hai nút bất kì.

Hệ thống đã bị xuống cấp, tất cả các tuyến đường cần được nâng cấp. Tuy nhiên trong một ngày chỉ có thể nâng cấp không quá k đường, đồng thời trong một ngày bất kì thì các đường được chọn nâng cấp không được đi qua, nhưng vẫn phải bảo đảm sự đi lại giữa hai nút bất kì. Cần lập kế hoạch sửa đường sao cho hoàn thành trong ít ngày nhất.

Dữ liệu vào: từ tệp văn bản SUADUONG.INP

+ Dòng đầu tiên chứa 3 số nguyên dương N M k

+ M dòng tiếp theo, mỗi dòng ghi u, v thể hiện đường nối giữa hai nút u, v.

Dữ liệu ra: Ghi vào tệp SUADUONG.OUT số p là số ngày ít nhất cần sửa chữa

Ví dụ:

SUADUONG.INP	SUADUONG.OUT	Giải thích
6 10 3 1 2 1 4 1 5 1 6 2 3 3 4 3 6 4 5 4 6 5 6	4	Ngày 1: (1 4) (1 5) (1 6) Ngày 2: (3 4) (3 5) (4 5) Ngày 3: (2 3) (4 6) (5 6) Ngày 4: (1 2)

Solution - Code - Test