Your program should read from an input file, which will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard. Input. txte2 e4a1 b2b2 c3a1 h8a1 h7h8 a1b1 c3f6 f6Output SpecificationFor each test case, print one line saying To get from xx to yy takes ?? knight moves. in console. Sample OutputBelow is the correct output for the previous sample input:To get from e2 to e4 takes 2 knight moves. To get from a1 to b2 takes 4 knight moves. To get from b2 to c3 takes 2 knight moves. To get from a1 to h8 takes 6 knight moves. To get from a1 to h7 takes 5 knight moves. To get from h8 to a1 takes 6 knight moves. To get from b1 to c3 takes 1 knight moves. To get from f6 to f6 takes 0 knight moves. Hints1. According to the problem description, the grid is 8 by 8, therefore there are 64 squares. We can then model the chessboard as a graph with 64 vertices; and an edge between two vertices exists if and only if we can make a knight move from one vertex to another.2. When moving to the next position, a knight can have at most eight possible directions, as shown in the above figure for the black knight, without getting out of the chess board boundary.3. The problem becomes a graph traversal problem!4. DFS or BFS? Which one will work?