Cho hai từ ~x~, ~y~ và một dãy hữu hạn các từ ~(w_{1}~, ~w_{2}~, ..., ~w_{k})~.
Phép toán ~p \times q~ mang ý nghĩa là phép nối từ ~p~ với từ ~q~, hay nói cách khác ~p \times q~ là một từ mới tạo thành bằng cách viết từ ~q~ phía sau từ ~p~. Ta cần kiểm tra xem hai từ ~x~, ~y~ có thể tương đương hóa bằng cách sử dụng các từ trong dãy cho trước không.
Ví dụ: Từ abba và ab có thể tương đương hóa bằng cách sử dụng các từ trong dãy: baaabad aa badccaa cc. Ta cần nối vào từ abba các từ: aa và badccaa, và nối vào từ ab các từ baaabad, cc và aa theo thứ tự. Trong cả hai trường hợp, ta sẽ thu được cùng một từ: abbaaabadccaa.
Cho biết từ ~x~, từ ~y~ và dãy từ ~w_{1}~, ~w_{2}~, ..., ~w_{k}~. Cho biết từ ~x~ và ~y~ có thể tương đương hóa bằng cách sử dụng các từ trong dãy cho trước được hay không? Nếu có thể, hãy tìm số lượng nhỏ nhất phép toán * cần sử dụng.
Input
- Dòng đầu tiên chứa một số nguyên dương ~k \leq 40~.
- Dòng thứ hai và dòng thứ ba mô tả từ ~x~ và ~y~.
- ~K~ dòng tiếp theo mô tả dãy từ ~w_{1}~, ~w_{2}~, ..., ~w_{k}~, mỗi từ trên một dòng.
- Mô tả của mỗi từ chứa một số nguyên cho biết độ dài của từ, theo sau bởi khoảng trắng và một chuỗi thể hiện từ đó.
- Mỗi từ chỉ bao gồm các chữ cái Latin in thường và có độ dài không vượt quá ~2000~.
- Tổng độ dài các từ không vượt quá ~5000~.
Output
- Nếu không tồn tại lời giải, in ra 'NIE'.
- Nếu tồn tại lời giải, in ra một số nguyên dương, là số lượng nhỏ nhất các phép toán ~\times~ cần để tương đương hóa hai từ ~x~ và ~y~.
Sample Input 1
4
4 abba
2 ab
7 baaabad
2 aa
7 badccaa
2 cc
Sample Output 1
5
Sample Input 2
4
1 a
2 ab
2 bb
2 ab
2 ba
2 aa
Sample Output 2
NIE
Comments