As a part of her research into the origin of Pokémon, Professor Juniper is studying a newly-discovered dictionary of words written in ancient Unown symbology. This enormous dictionary contains thousands of words, some of which are thousands of symbols in length. But, most surprisingly, the dictionary uses a large number of never-before-seen Unown symbols, one million of them to be exact, which Professor Juniper has enumerated in the range $$$[0, 10^6)$$$.
As part of her unorthodox research methods, Professor Juniper has decided to play "word ladder" with these Unown words. This is a game where you start with a word from the dictionary and you can perform the following operation any number of times: change a single symbol in your current word as long as the resultant word also exists in the dictionary. Often, the word ladder will have a goal, like getting from "peek" to "hear". In this example, you can go from "peek" to "peel" to "heel" to "heal" to "hear". The score of a word ladder game is the number of operations performed to get from the start to the end, with a lower number being more desirable.
As the professor's favorite data analyst, she wants you to develop an algorithm for finding the lowest word ladder score on a given set of Unown words. More specifically, Professor Juniper gives you a "subdictionary" of $$$n$$$ words – represented as arrays – all with equal length $$$m$$$, and she wants you to find the length of the shortest sequence of legal change operations to get from the first word to the last word. If no such sequence exists, report $$$-1$$$.
Initial analysis shows that the words in the dictionary vary significantly, such that no word can produce $$$100$$$ or more other words in a single operation.
The first line contains two integers $$$n$$$ and $$$m$$$ $$$(2 \le n, m \le 10^5, n \times m \le 10^6)$$$ – the number of words in the subdictionary and the length of the words, respectively.
The following $$$n$$$ lines each contain $$$m$$$ space-separated integers that define an Unown word. The $$$j$$$th integer on the $$$i$$$th line is $$$A[i][j]$$$ $$$(0 \le A[i][j] \lt 10^6)$$$. Each word is distinct, i.e. no two words are completely equal.
It is guaranteed that, for any $$$A[i]$$$, the number of words in the subdictionary that $$$A[i]$$$ can produce with a single-element change is less than $$$100$$$.
Output a single integer, the number of operations required to get from $$$A[0]$$$ to $$$A[n-1]$$$ with the above rules. If there is no way to get to $$$A[n-1]$$$, output $$$-1$$$.
8 41 2 3 41 2 4 31 2 3 30 2 3 40 1 3 30 2 3 33 2 3 33 3 3 3
3
4 310 10 1010 20 1020 10 2020 20 20
-1
