Given beginWord, endWord, and a wordList, find all shortest transformation sequences from beginWord to endWord, where each step changes exactly one letter and every word must be in wordList.

Example 1:

Input: beginWord="hit", endWord="cog", wordList=["hot","dot","dog","lot","log","cog"]
Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]

Example 2:

Input: beginWord="hit", endWord="cog", wordList=["hot","dot","dog","lot","log"]
Output: []

Constraints:

• 1 <= beginWord.length <= 5
• 1 <= wordList.length <= 500