Description

A hacker tries to access the system. The initial password must be transformed to the target password. Only one character can be changed at a time. The changed password must exist in the valid password list. Find the minimum number of transformations.

Input

Output

Constraints

• •1 ≤ word length ≤ 10
• •1 ≤ number of words ≤ 50
• •begin ≠ target
• •All words have same length

Examples

begin = "cat", target = "dog", words = ["cot", "dot", "dog", "dat", "dag"]

3