Một phương pháp tổng hợp chuỗi DNA mới từ hai chuỗi DNA chỉ gồm các ký tự A, T, G, C đã được phát triển. Nếu phần đầu của một chuỗi và phần cuối của chuỗi kia có một đoạn chung liên tiếp gồm ít nhất một ký tự, ta có thể nối hai chuỗi bằng cách gộp hai đoạn chung này thành một.

Ví dụ, TTTATGC và ATGCAAA có đoạn chung ATGC ở cuối chuỗi thứ nhất và đầu chuỗi thứ hai, nên có thể nối chúng để tổng hợp chuỗi TTTATGCAAA. Ngoài ra, từ hai chuỗi AAA, ta có thể tổng hợp được cả chuỗi AAAA lẫn chuỗi AAAAA.

Để phát triển một loại thuốc mới, người ta muốn tổng hợp một chuỗi DNA nhất định từ các chuỗi DNA cơ sở có trong phòng thí nghiệm.

Yêu cầu

Phòng thí nghiệm có \(N\) loại chuỗi DNA cơ sở. Hãy viết chương trình tìm số chuỗi DNA cơ sở ít nhất cần dùng để tổng hợp chuỗi DNA đích bằng phương pháp nối trên. Nguồn dự trữ các chuỗi DNA cơ sở rất dồi dào, nên có thể sử dụng cùng một loại bao nhiêu lần tùy ý. Trong mọi bộ dữ liệu chấm, luôn tồn tại một cách kết hợp các chuỗi DNA cơ sở để thu được chuỗi DNA đích.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa số nguyên \(N\).
• Dòng thứ hai chứa một xâu chỉ gồm các ký tự A, T, G, C, biểu diễn chuỗi DNA đích.
• Trong \(N\) dòng tiếp theo, mỗi dòng chứa một xâu chỉ gồm các ký tự A, T, G, C, biểu diễn một loại chuỗi DNA cơ sở. Không có hai chuỗi DNA cơ sở trùng nhau trong danh sách này.

Dữ liệu ra

In ra đầu ra chuẩn một số nguyên là số chuỗi DNA cơ sở ít nhất cần dùng.

Ràng buộc

• Giới hạn trong kỳ thi gốc: thời gian \(1\) giây, bộ nhớ \(64\) MB.

• Trong kỳ thi gốc, kích thước ngăn xếp (stack) chỉ bị giới hạn bởi giới hạn bộ nhớ của bài, không có giới hạn riêng nhỏ hơn.

• Số loại chuỗi DNA cơ sở \(N\) không vượt quá \(50\,000\).

• Độ dài chuỗi DNA đích không vượt quá \(150\,000\).
• Độ dài mỗi chuỗi DNA cơ sở không vượt quá \(20\).

Phân nhóm

Bài này có tổng cộng \(100\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm.

• Nhóm test trị giá \(30\) điểm: \(N\) và độ dài chuỗi DNA đích đều không vượt quá \(1\,000\).

Ví dụ

5
ATATATGCCCAT
ATAT
ATG
GCCC
GCCCAT
CAT

4

1
AAAAAAAAAA
AAA

5

2
ATATATATAT
ATA
TAT

5