Tương đương hóa hai từ

View as PDF

Submit solution

Points: 1.03 (partial)
Time limit: 0.4s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Polish OI 3
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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

Please read the guidelines before commenting.


There are no comments at the moment.