BÀI 3. CHIẾN TRANH (CHIENTRANH.*) Có L quốc gia đi chinh phạt các vùng đất mới. Cụ thể, có N thành phố được kết nối với nhau bằng những con đường hai chiều. Tại thời điểm 0, quốc gia i đang chiếm đóng thành phố cô và các quốc gia bắt đầu đi chinh phạt các vùng đất mới theo quy tắc sau: Dòng đầu tiên chứa N, L, M ( l <= N <= 10 ^ 5 , 2 <= L <= 50 1 <= M <= 10 ^ 5 ) 1. Nếu một quốc gia chiếm đóng được một thành phố, họ sẽ cử các chiến binh di chuyển đến các thành phố khác có đường đi với thành phố vừa chiếm đóng, tất cả đều di chuyển cùng tốc độ. 2. Nếu các chiến binh của hai quốc gia khác nhau gặp nhau trên một con đường, họ sẽ chiến đấu với nhau mãi mãi trên con đường đó. 3. Nếu các chiến binh của hai quốc gia khác nhau tới một thành phố cùng một lúc, họ sẽ chiến đấu với nhau mãi mãi trên thành phố đó. 4. Nếu các chiến binh của một quốc gia đến thành phố đang có chiến tranh xảy ra thì họ cũng tham gia vào cuộc chiến. 5. Nếu các chiến binh đến một thành phố chưa có quốc gia nào khác chiếm đóng thì họ sẽ chiếm đóng thành phố này và tiếp tục cử các chiến binh di chuyển đến các thành phố khác như quy tắc 1. Chú ý: với các quy tắc trên thì chỉ có duy nhất một quốc gia chiếm được một thành phố. Nếu chiến binh của hai quốc gia cùng đến một thành phố thì họ sẽ chiến đấu mãi mãi ở thành phố đó mà không di chuyển đến các thành phố khác. Hãy xác định các cặp quốc gia chiến đấu với nhau. Lưu ý: các quốc gia đánh số từ 0 tới L - 1, các thành phố được đánh số từ 0 tới N – 1. Dữ liệu: Vào từ file văn bản CHIENTRANH.INP L dòng tiếp theo chứa cị là thành quốc gia i chiếm ban đầu. M dòng tiếp theo mỗi dòng chứa ba số nguyên u, v, w mô tả một con đường giữa hai thành phố u và v có thời gian di chuyển là w (0 ≤uv<N, l <= w <= 2000 ). Dữ liệu đảm bảo không có đường đi nào nổi một thành phố với chính nó, không có nhiều hơn một đường đi nổi hai thành phố. Kết quả: Ghi ra file văn bản CHIENTRANH.OUT Ghi ra nhiều dòng, mỗi dòng là hai số a, b mô tả quốc gia a sẽ chiến đấu với quốc gia b (a < b). Các cặp được liệt kê theo thứ tự từ điển. Ví dụ: CHIENTRANH.INP CHIENTRANH.OUT 848 01 0 03 2 12 4 01 100 23 6 12 100 23 100 3 4 100 45 100 5 6 100 6 7 100 70 1000 Ràng buộc: 1. 20% số điểm có đồ thị là một đường thẳng (0, 1), (1, 2) ,...,(N-2,N-1) 2. 20% số điểm có w = 1 3. 20% số điểm không có chiến tranh tại các thành phố 4. 20% số điểm có 1 <= N M <= 2000 5. 20% số điểm còn lại không có ràng buộc gì thêm.
