#1506 · Mạng rút gọn

Một hệ thống gồm n máy tính được nối thành một mạng có m kênh nối, mỗi kênh nối hai máy tính trong mạng, giữa hai máy tính có không quá 1 kênh nối. Các máy tính được đánh số từ 1 đến n và các kênh nối được đánh số từ 1 tới m. Việc truyền tin trực tiếp có thể thực hiện được đối với hai máy có kênh nối. Các kênh nối trong mạng được chia ra làm ba loại 1, 2, 3.

Ta nói giữa hai máy a và b trong mạng có đường truyền tin loại k, (k \in 1, 2) nếu tìm được dãy các máy a = v_1, v_2,...,v_p = b thoả mãn điều kiện: giữa hai máy v_i và v_i + _1 hoặc có kênh nối loại k, hoặc có kênh nối loại 3, (i = 1, 2, ..., p-1).

Yêu cầu: Cần tìm cách loại bỏ khỏi mạng một số nhiều nhất kênh nối nhưng vẫn đảm bảo luôn tìm được cả đường truyền tin loại 1 lẫn đường truyền tin loại 2 giữa hai máy bất kỳ trong mạng.

• Dòng một chứa hai số n, m cách nhau một dấu cách;
• Dòng thứ i trong số m dòng tiếp theo chứa ba số nguyên dương u_i, v_i, s_i cho biết kênh truyền tin thứ i là kênh loại s_i nối hai máy u_i và v_i.

• Dòng đầu tiên ghi r là số kênh cần loại bỏ. r = -1 nếu trong mạng đã cho tồn tại hai máy không có đường truyền tin loại 1 hoặc loại 2.
• Nếu r > 0 thì r dòng tiếp theo, mỗi dòng ghi chỉ số của một kênh cần loại bỏ.

Lưu ý: Dữ liệu mẫu chỉ mang tính chất tham khảo, các chỉ số các kênh cần loại bỏ có thể không cần theo thứ tự