One of the common puzzles you may find in puzzle magazines is to take 2 4-letters words – let’s use "lion" and "lamb" for our example – and create a chain of words that lead from "lion" to "lamb" by changing one character with each step. for instance, we can get from "lion" to "lamb" like this: lion loon loot lost lose lase lame lamb likewise, the path from "love" to "hate" could be: love hove have hatein this assignment, you’re going to write a program to find these paths. on d2l, in the section for this assignment, you’ll find two files: words4.txt – this is a sorted list of 1778 4-letter words, one per line. wordgraph. txt – this is a graph data file, in the format used by examples in the book, containing an edge for all pairs of words in words4.txt that differ by one letter. this is suitable as input to graph constructor that takes an input stream. for example, the first few lines of words4.txt are: abbe abed abet ableif we read words4.txt into an array of strings, abbe would be entry 0, abed would be entry 1, etc. these indices are the same as the node numbers in wordgraph. txt. so, since abbe and able differ by one character, there is an edge in wordgraph. txt between vertices 0 and 3. likewise, since abed and abet differ by one character, these is an edge between vertices 1 and 2. and indeed, the first few lines of wordgraph. txt are (recall that the first two lines are the number of vertices and the number of edges): 1778 6525 03 12the assignment is to read these two files into appropriate data structures, and then read pairs of words from standard input. for each pair of words, you will print out the shortest path between them that can be created by changing one letter at a time. here is the basic outline of what needs to be done: read words4.txt (you may find in. readallstrings() to be useful) create a graph using wordgraph. txtwhile there is input available from stdinread two wordsmap the words to graph indicesuse the indices to compute the shortest path map the path indices back to wordsprint the path from the first word to the secondnote that you need to map array indices to words, and words to array indices. think about how you might do that. hint: all the words are known ahead of time, and are already sorted, so there’s a relatively simple way to do this. you may use any code from the algs4 library or our stdarray class that you deem useful. both are provided for you on zybooks. this means you do not have to implement your own code for creating or searching a graph; everything you need is provided. your entire program may be in your main() method. you may find the sample paths program on page 535 useful. remember you want the shortest path, so pick the appropriate paths implementation (depthfirstpaths or breadthfirstpaths) to do that. (for giggles, try the wrong one and see what happens.)the output should be formatted like this: lion -> lamblion loon loot lost lose lase lame lambnote that zybooks will expect a single space between each word, and an extra space after the last item in the list. note: there is a small chance that your output may not find the exact same path as zybooks is expecting. if that’s the case, email me to let me know, but as long as it found a valid path, you’re probably okay. to get you started, the next page contains the shell of the program you need to write. import edu. princeton. cs. algs4.*; public class wordpath {public static void main(string[] args) {in flw = new in("words4.txt"); /* read the word list into an appropriate data structure. */ /* keep it simple! */in wg = new in("wordgraph. txt"); graph g = new graph(wg); while (! stdin. {string from = stdin. readstring(); string to = stdin. readstring(); int idxfrom = /* find the vertex number of the "from" word */ int idxto = /* find the vertex number of the "to" word *//* compute the shortest paths from idxfrom */if (/* there is no path to idxto */)stdout. println("no path! "); else {} }} }stdout. printf("%s -> %s\n", from, to); /* get the path from idxfrom to idxto, */ /* and print each vertex in the path */