Sau bao đêm thâu thức trắng luyện code, sau chuỗi ngày dài luyện với giáo sư, sau những buổi no nê trà sữa, cuối cùng ngày thi học sinh giỏi quốc gia cũng thực sự đến rồi...
Như khâu chuẩn bị cuối cùng cho ngày trọng đại, đội tuyển HSG Tin học thị trấn Mù Căng Chải quyết định đi xem bói, nhờ thầy bói chỉ giúp cách bố trí chỗ ngồi cho hợp phong thủy. Sau khi xem số mệnh của từng người, thầy bói phán những điều sau đây:
thí sinh của trường thuộc một trong ba mệnh: Thủy, Mộc và Hỏa.
Các thí sinh cùng một mệnh thì phải ngồi chung phòng
Có cặp thí sinh xung khắc. Hai thí sinh ở mọi cặp đều không cùng mệnh.
Hai thí sinh xung nhau thì không được ngồi chung phòng.
Do điều kiện cơ sở vật chất thiếu thốn, trường THPT chuyên thị trấn Mù Căng Chải chỉ có hai phòng để tổ chức thi học sinh giỏi tin học. Bởi thế, đôi lúc việc đáp ứng đủ mọi nhu cầu của thầy bói là bất khả thi. Nhà trường buộc phải đuổi một số thí sinh ra khỏi đội tuyển, để các thí sinh còn lại có thể xếp vào hai phòng mà tránh gặp xui xẻo.
Bạn hãy giúp nhà trường loại đi ít thí sinh nhất, sao cho các thí sinh không bị loại có thể xếp vào hai phòng thỏa mãn mọi yêu cầu của thầy bói.
Dữ liệu vào:
Dòng đầu tiên chứa số nguyên là số thí sinh trong đội tuyển.
Dòng thứ hai chứa xâu gồm kí tự thể hiện mệnh của thí sinh ( đại diện cho Hỏa, đại diện cho Mộc và đại diện cho Thủy).
Dòng thứ ba chứa số nguyên là số cặp thí sinh xung khắc.
dòng còn lại, mỗi dòng gồm hai số nguyên và thể hiện một cặp thí sinh xung khắc. Hai thí sinh và không cùng mệnh với nhau.
Dữ liệu ra:
Gồm một dòng duy nhất chứa số thí sinh ít nhất cần bị loại bỏ.
