Tèo thiết kế một hệ thống mã hóa bảo mật cho kho lưu trữ cổ phiếu dạng chuỗi ký tự. Mỗi mã sản phẩm là một từ có độ dài 5 ký tự.

Tèo cần tìm cách biến đổi mã nguồn beginWord thành mã đích endWord thông qua một chuỗi các mã trung gian sao cho:

1. Mỗi bước biến đổi chỉ được thay đổi đúng 1 ký tự.
2. Mọi mã trung gian được tạo ra phải nằm trong danh sách các mã hợp lệ được cung cấp sẵn.

Hãy tìm số lượng mã (bao gồm cả beginWord và endWord) trong chuỗi biến đổi ngắn nhất, hoặc in ra 0 nếu không thể thực hiện biến đổi.

Định dạng đầu vào

• Dòng đầu chứa hai chuỗi ký tự beginWord và endWord.
• Dòng thứ hai chứa số nguyên \(N\) (\(1 \le N \le 5000\)) là số từ hợp lệ.
• \(N\) dòng tiếp theo, mỗi dòng chứa một từ hợp lệ có độ dài bằng nhau và \(\le 10\).

Định dạng đầu ra

• Một số nguyên duy nhất là số bước trong chuỗi biến đổi ngắn nhất.

Ví dụ

Input:

hit cog
5
hot
dot
dog
lot
log

Output:

5