Giáo sư X đang nghiên cứu về hệ sinh thái trên hai hành tinh Alpha và Beta. Nghiên cứu đòi hỏi 𝑛 thí nghiệm đánh số từ 1 tới 𝑛. Mỗi thí nghiệm được gán nhãn bằng một chữ cái ∈ {A,B,C}:

A: Thí nghiệm chỉ có thể thực hiện trên hành tinh Alpha
B: Thí nghiệm chỉ có thể thực hiện trên hành tinh Beta
C: Thí nghiệm có thể thực hiện trên hành tinh Alpha hay Beta đều được.

Ngoài ra quy trình thí nghiệm cần phải thỏa mãn 𝑚 ràng buộc. Ràng buộc thứ 𝑖 được cho bởi cặp số nguyên (𝑥_𝑖, 𝑦_𝑖) với ý nghĩa: Thí nghiệm 𝑦_𝑖 chỉ có thể thực hiện khi thí nghiệm 𝑥_𝑖 đã xong và cho kết quả.

Yêu cầu: Vì việc đi lại giữa hai hành tinh khá tốn kém và mệt mỏi, hãy lập một kế hoạch làm thí nghiệm cho giáo sư X để số lần di chuyển giữa hai hành tinh Alpha và Beta là nhỏ nhất. Giả sử ban đầu giáo sư X đang ở hành tinh Alpha.

Dữ liệu: 

- Dòng 1 chứa hai số nguyên dương 𝑛, 𝑚 ≤ 10⁵ cách nhau bởi dấu cách
- Dòng 2 chứa 𝑛 ký tự ∈ {A,B,C} liền nhau, ký tự thứ 𝑘 là nhãn của thí nghiệm 𝑘
- 𝑚 dòng tiếp theo, dòng thứ 𝑖 chứa hai số nguyên 𝑥_𝑖, 𝑦_𝑖 cách nhau bởi dấu cách ứng với một ràng buộc

Kết quả:

Ghi ra một số nguyên duy nhất là số lần di chuyển giữa hai hành tinh Alpha và Beta theo phương án tìm được. Ghi số -1 nếu không thể thực hiện được tất cả các thí nghiệm trong nghiên cứu