Giải bài trực tuyến

Cho hai từ x, y và một dãy hữu hạn các từ (w₁, w₂, ..., w_k).

Phép toán p * q mang ý nghĩa là phép nối từ p với từ q, hay nói cách khác p * 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.

Yêu cầu

Cho biết từ x, từ y và dãy từ w₁, w₂, ..., 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.

Dữ liệu

• Dòng đầu tiên chứa một số nguyên dương k ≤ 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₁, w₂, ..., 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.

Kết quả

• 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 * cần để tương đương hóa hai từ x và y.

Ví dụ

Dữ liệu
4
4 abba
2 ab
7 baaabad
2 aa
7 badccaa
2 cc

Kết quả
5

Dữ liệu
4
1 a
2 ab
2 bb
2 ab
2 ba
2 aa

Kết quả
NIE