Sau khi ở bên những con bò quá lâu, Farmer John đã bắt đầu hiểu ngôn ngữ của chúng. Hơn nữa, ông nhận thấy trong số \(N\) con bò (\(2 \le N \le 1000\)), một số luôn nói thật, còn những con khác luôn nói dối.

FJ cẩn thận lắng nghe \(M\) phát biểu (\(1 \le M \le 10\,000\)) từ những con bò, mỗi phát biểu có dạng x y T, nghĩa là "bò \(x\) khẳng định bò \(y\) luôn nói thật", hoặc x y L, nghĩa là "bò \(x\) khẳng định bò \(y\) luôn nói dối". Mỗi phát biểu liên quan đến một cặp bò khác nhau, và cùng một cặp bò có thể xuất hiện trong nhiều phát biểu.

Không may, FJ cho rằng mình có thể đã ghi sai một số mục trong danh sách, nên có thể không tồn tại cách hợp lệ để xác định mỗi con bò là bò nói thật hay bò nói dối mà nhất quán với cả \(M\) phát biểu trong danh sách của FJ. Để giúp FJ tận dụng được nhiều nhất có thể từ danh sách, hãy tính giá trị \(A\) lớn nhất sao cho tồn tại một cách hợp lệ để xác định mỗi con bò là bò nói thật hoặc bò nói dối, đồng thời nhất quán với \(A\) mục đầu tiên trong danh sách của FJ.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), cách nhau bởi dấu cách.
• \(M\) dòng tiếp theo, mỗi dòng có dạng x y L hoặc x y T, mô tả một phát biểu của bò \(x\) về bò \(y\).

Dữ liệu ra

In ra giá trị \(A\) lớn nhất sao cho \(A\) mục đầu tiên trong danh sách của FJ có thể nhất quán với một cách gán trạng thái "nói thật" hoặc "nói dối" nào đó cho \(N\) con bò.

Ví dụ

4 3
1 4 L
2 3 T
4 1 T

2

Nguồn

USACO 2013 January Contest, Bronze — Problem 3: Liars and Truth Tellers

Tác giả đề: Brian Dean, 2013.