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

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

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 \leq N \leq 1000$ , $1 \leq M \leq 10 000$ )
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 \leq N \leq 1000$
$1 \leq M \leq 10 000$

Ví dụ

Input	Output	Giải thích
4 3 1 4 L 2 3 T 4 1 T	2	Phát biểu 1 và 3 mâu thuẫn nhau, nhưng phát biểu 1 và 2 tương thích (người 1,2,3 nói thật, người 4 nói dối)
10 20 4 1 L 3 9 L 10 5 L 10 8 L 7 9 T 5 2 T 9 4 L 4 3 T 6 3 T 4 7 L 10 2 L 3 1 T 3 2 T 4 1 T 6 3 L 6 8 L 5 2 L 5 9 T 6 4 L 4 5 L	11	11 phát biểu đầu tiên có thể thỏa mãn đồng thời

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".

Bình luận

Không có bình luận tại thời điểm này.