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