Mô tả và yêu cầu

Trò chơi ghép từ

An và Bình cùng nhau học từ mới bằng chơi trò chơi ghép từ trên tập gồm 𝑛 từ: 𝑤1, 𝑤2, ..,𝑤𝑛 như
sau:

- Ban đầu An sẽ lựa chọn một từ bất kỳ trong tập,
- Sau đó Bình và An lần lượt thay phiên nhau tìm một từ trong tập mà ký tự đầu tiên của từ
bằng ký tự cuối cùng của từ mà người trước đó vừa chọn, rồi ghép nối tiếp. Mỗi từ có thể
được sử dụng nhiều lần.

Ví dụ: Nếu ban đầu An chọn từ “ab”, tiếp đến Bình chọn từ “bcb”, rồi lại đến lượt An chọn từ “ba”
thì 2 bạn sẽ nhận được dãy các ký tự sau: “abbcbba”.

Dãy các ký tự mà An và Bình tạo ra được gọi là chứa từ khóa 𝑠 nếu từ dãy ký tự đó có thể nhận
được 𝑠 bằng cách xóa đi một số ký tự (hoặc giữ nguyên). Dãy ký tự tạo thành là một xâu đối xứng
nếu đọc dãy ký tự từ trái qua phải cũng giống như đọc từ phải qua trái.

Với ví dụ trên thì dãy ký tự chứa từ khóa “abcba” và là một xâu đối xứng.

Yêu cầu: Cho tập gồm 𝑛 từ và từ khóa 𝑠, hỏi độ dài của dãy ký tự mà An và Bình tạo ra để chứa
từ khóa 𝑠 và là một xâu đối xứng ngắn nhất là bao nhiêu?

Dữ liệu vào

- Dòng 1: từ khóa 𝑠 chỉ gồm các ký tự ‘a’ đến ‘z’;
- Dòng 2: số nguyên 𝑛 là số từ trong tập;
- 𝑛 dòng tiếp, mỗi dòng một từ (độ dài không vượt quá 10, chỉ gồm các ký tự ‘a’ đến ‘z’).

Dữ liệu ra

- Gồm một dòng chứa độ dài ngắn nhất tìm được, nếu không có nghiệm ghi -1

WORDGAME.INP WORDGAME.OUT
abcba 7
4
ab
bcb
ba
aa
abcba -1
3
ab
ba
aa
aaaaa 6
1
aa
Subtask 1: 𝑛 ≤ 2 và độ dài xâu 𝑠 không vượt quá 5;

Subtask 2: 𝑛 ≤ 100, độ dài xâu 𝑠 không vượt quá 50 và độ dài các từ đều bằng 3;

Subtask 3: 𝑛 ≤ 100, độ dài xâu 𝑠 không vượt quá 50;