Determine the Edit Distance in a Word Ladder

Each operation replaces one character, and every word passed through must be in the word list (the start word need not be). If the target word is not in the word list there is no solution, but when the start and target are identical no operation is needed. Find the minimum number of replacements.

输入格式

The input is a JSON array [begin,end,wordList]. The original gives no bounds on length, characters or count; this site sets each word to 1..20 Unicode scalars and the word list to 0..10000 entries, and the start and target words may differ in length. All code points total ≤200040, and standard JSON preserves whitespace/NUL. Words of different lengths cannot reach each other by replacement; if there is no solution, output −1.

输出格式

Output a single integer answer.

样例 1

输入：

["hit","cog",["hit","hot","dot","dog","cog"]]

输出：

4

样例 2

输入：

["word","word",["word","ward"]]

输出：

0

样例 3

输入：

["hit","cog",["hit","hot","dot","dog"]]

输出：

-1

样例说明

The outputs of the three public examples are, in order: 4; 0; -1. Verified by independent enumeration or direct simulation.