Người Nói Thật và Người Nói Dối

Có $N$ người, mỗi người hoặc luôn nói thật hoặc luôn nói dối. Có $M$ phát biểu, phát biểu thứ $i$ có dạng "người $x$ nói rằng người $y$ là người nói thật (T) hoặc nói dối (L)".

Nếu $x$ là người nói thật thì phát biểu của $x$ đúng. Nếu $x$ là người nói dối thì phát biểu của $x$ sai (tức là thực tế ngược lại với những gì $x$ nói).

Hãy tìm số nguyên $A$ lớn nhất sao cho tồn tại một cách phân loại $N$ người thành "nói thật" và "nói dối" thỏa mãn đồng thời tất cả $A$ phát biểu đầu tiên.

Dữ liệu vào

• Dòng 1: Hai số nguyên $N$ và $M$ ($2\le N\le 1000$, $1\le M\le 10000$)
• Dòng $2$ đến $M+1$: Mỗi dòng gồm $x$, $y$ và ký tự "T" hoặc "L" mô tả phát biểu thứ $i$

Dữ liệu ra

Một số nguyên duy nhất: giá trị $A$ lớn nhất.

Ràng buộc

• $2\le N\le 1000$
• $1\le M\le 10000$

Ví dụ

Ghi chú

"x y T" nghĩa là $x$ tuyên bố "$y$ là người nói thật". "x y L" nghĩa là $x$ tuyên bố "$y$ là người nói dối".