Word Transformation

You are given a dictionary of words and two words: a start word and an end word. Your task is to determine the minimum number of transformations required to change the start word into the end word. In each transformation, you may change exactly one letter of the current word, and the resulting word must exist in the dictionary.

If it is impossible to transform the start word into the end word under these constraints, output -1. Note that all words (including the start word, end word, and dictionary words) have the same length.

inputFormat

Input is read from standard input (stdin). The input consists of four parts:\n1. An integer n that denotes the number of words in the dictionary.\n2. A line with n space-separated words representing the dictionary.\n3. A line containing the start word.\n4. A line containing the end word.

outputFormat

Output the minimum number of transformations required to transform the start word into the end word. If no valid transformation sequence exists, output -1. The output is written to standard output (stdout).## sample

6
hot dot dog lot log cog
hit
cog

4