Babel

Nguồn: UVa Online Judge

Phiên bản: Phước Hưng OJ Extended

Đề bài

John ghi lại $M$ từ. Mỗi từ được gắn với hai ngôn ngữ khác nhau mà từ đó cùng xuất hiện trong từ vựng.

Cho ngôn ngữ bắt đầu $O$ và ngôn ngữ đích $D$. Cần chọn một dãy từ sao cho:

• từ đầu tiên thuộc ngôn ngữ $O$;
• từ cuối cùng thuộc ngôn ngữ $D$;
• hai từ liên tiếp cùng thuộc ít nhất một ngôn ngữ;
• hai từ liên tiếp không được bắt đầu bằng cùng một chữ cái.

Chi phí của dãy là tổng số ký tự của các từ được chọn. Hãy tìm chi phí nhỏ nhất.

Input

Dòng đầu chứa số nguyên $M$.

Dòng thứ hai chứa hai chuỗi khác nhau $O,D$.

Trong $M$ dòng tiếp theo, mỗi dòng chứa ba chuỗi $I_1,I_2,P$: hai ngôn ngữ khác nhau và một từ chung của hai ngôn ngữ đó.

Tất cả các chuỗi có độ dài từ $1$ đến $50$ và chỉ gồm các chữ cái thường a–z.

Một cặp ngôn ngữ có thể có nhiều từ chung, nhưng cùng một từ $P$ không bao giờ xuất hiện hai lần trong một test case.

Phiên bản Phước Hưng OJ chứa đúng một test case; dòng kết thúc 0 của đề gốc đã được loại bỏ.

Output

In tổng số ký tự nhỏ nhất của một dãy thỏa mãn các yêu cầu.

Nếu không tồn tại dãy hợp lệ, in impossivel.

Subtask

Trong tất cả các Subtask: $O\ne D$; $I_1\ne I_2$; mọi chuỗi có độ dài từ $1$ đến $50$ và chỉ gồm chữ thường a–z; mỗi từ $P$ xuất hiện nhiều nhất một lần.

• Subtask 1 — 20% — 0.75 giây: $1\le M\le100$.
• Subtask 2 — 30% — 1.50 giây: $1\le M\le1000$.
• Subtask 3 — 50% — 3.00 giây: $1\le M\le2000$.

Ví dụ

Input

4
portugues frances
ingles espanhol red
espanhol portugues amigo
frances ingles date
espanhol ingles actual

Output

12

Giải thích

Một dãy hợp lệ là amigo red date:

• amigo liên kết portugues với espanhol;
• red liên kết espanhol với ingles;
• date liên kết ingles với frances.

Ba từ bắt đầu lần lượt bằng a, r, d, nên không có hai từ liên tiếp cùng chữ cái đầu. Tổng số ký tự là $5+3+4=12$.