Hội hoa xuân

View as PDF

Submit solution

Points: 1.23 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Based on a problem from ACM
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Tết năm nay Nuga cùng bạn đi xem lễ hội hoa ở Hà Nội. Nuga rất hứng thú với hàng trăm loài hoa đẹp được trình diễn ở đây, đặc biệt là cuộc thi Đào -- Mai để chọn ra một cây hoa đẹp nhất.

Có ~D~ cây đào (đánh số từ ~1~ đến ~D~) và ~M~ cây mai (đánh số từ ~1~ đến ~M~) tham gia cuộc thi. Vòng đầu tiên sẽ do khán giả bình chọn. Có ~N~ khán giả, mỗi người sẽ bỏ một lá phiếu. Điều đặc biệt là mỗi lá phiếu chỉ thuộc một trong ~2~ dạng:

- "Chọn cây đào i, không chọn cây mai j".

hoặc

- "Chọn cây mai i, không chọn cây đào j".

Ban tổ chức muốn chọn ra danh sách một số cây lọt vào vòng ~2~ sao cho số khán giả có lá phiếu đúng (chính xác cả cây được chọn và cây không được chọn) là nhiều nhất.

Biết Nuga giỏi lập trình nên BTC vừa nhờ bạn ấy giải quyết bài toán khó này. Nhưng do mải ngắm hoa quá nên Nuga quên hết kiến thức mất rồi. Các bạn hãy giúp bạn ấy với nhé!

Input

  • Dòng đầu ghi ~T~ là số bộ test. ~( T \le 30)~ Mỗi bộ test bắt đầu bằng ~3~ số nguyên dương ~D, M, N~. ~(1 \le D, M, N \le 500)~
  • ~N~ dòng tiếp theo, dòng thứ ~k~ mô tả lá phiếu do khán giả thứ ~k~ bình chọn. Lá phiếu có dạng ~D_i~ ~M_j~ (Chọn cây đào ~i~, không chọn cây mai ~j~) hoặc ~M_i~ ~D_j~ (Chọn cây mai ~i~, không chọn cây đào ~j~), trong đó ~i~ và ~j~ là ~2~ số nguyên dương.

Output

  • Một dòng duy nhất chứa một số nguyên thể hiện số lượng nhiều nhất khán giả có lá phiếu đúng.

Giới hạn

  • ~T \leq 30~
  • ~1 \leq D~, ~M~, ~N \leq 500~

Sample Input

1
1 2 4
D1 M1
D1 M1
D1 M2
M2 D1

Sample Output

3

Comments

Please read the guidelines before commenting.


There are no comments at the moment.