Giao Hai Matroid - Rừng Cây Đa Sắc Cực Đại (Colorful Forest)

Mô tả bài toán

Cho một đồ thị vô hướng G = (V, E) gồm N đỉnh và M cạnh. Mỗi cạnh e_i = (u_i, v_i) được tô một màu nguyên dương c_i.

Một tập cạnh S ⊆ E được gọi là Rừng Cây Đa Sắc nếu thỏa mãn đồng thời hai điều kiện:

• Tập cạnh S không chứa chu trình vô hướng (tức là đồ thị con sinh bởi S là một rừng cây - Graphic Matroid).
• Không có hai cạnh nào trong S có cùng màu (tức là mỗi màu xuất hiện tối đa 1 lần - Partition Matroid).

Hãy tìm kích thước cực đại (số lượng cạnh tối đa) của một Rừng Cây Đa Sắc.

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: 1500ms.
• 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ả.