#2007. IMGAME

Bạn đang thiết kế một trò chơi khá đơn giản. Trong trò chơi này người chơi sẽ chọn một xâu kí tự tùy ý độ dài và tất cả các chữ cái là A, B, C hoặc D. Mỗi xâu này sẽ được tô một màu do bạn lựa chọn. Để giành chiến thắng người chơi cần thao tác một số phép biến đổi để thu được một xâu khác có cùng màu. Ở mỗi bước, một trong hai thao tác sau được phép thực hiện:

• Đổi chỗ kí tự kề nhau.
• Thay thế một xâu con của xâu thành xâu với nào đó (hai xâu này có cùng độ dài).

Bạn dự định thiết kế trạng thái “Bất khả thi” trong trò chơi này, tức là người chơi không có cách nào chiến thắng bất kể họ chọn xâu nào lúc đầu. Tính số màu tối thiểu bạn cần để làm được việc này.

Lưu ý: đáp số luôn tồn tại do bạn có thể đơn giản tô mỗi xâu độ dài với một màu khác nhau.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số và lần lượt là độ dài xâu và số lượng cặp ;
• Dòng thứ hai chứa xâu ;
• Dòng thứ ba chứa xâu ;
• Với mỗi , xâu và có độ dài như nhau. Hơn nữa, các xâu này chỉ chứa các kí tự A, B, C, D.

Dữ liệu ra:

• In ra số màu ít nhất cần sử dụng để tạo ra trạng thái Bất khả thi.

Ví dụ:

Dữ liệu vào:

1 1
A
B

Dữ liệu ra:

2

Dữ liệu vào:

2 3
A A D
B C D

Dữ liệu ra:

5

Dữ liệu vào:

2 3
B C D
C D B

Dữ liệu ra:

9

Dữ liệu vào:

6 6
AABBC AAAADA AAACA CABAA AAAAAA BAAAA
AACCB DAAABC AAAAD ABCBA AABAAA AACAA

Dữ liệu ra:

499

Giải thích:

• Trong test ví dụ đầu tiên, đương nhiên xâu và phải khác màu nhau, nên ít nhất hai màu cần được sử dụng. Đây cũng là phương án tối ưu.