Refer to image and answer with example output! Write a Lisp program to solve the Missionaries & Cannibals problem using depth-firstsearch. Your program should be invoked by the function call> (mac start end)where start is the current state of the problem and end is the desired goal state. Yourprogram should output the sequence of moves necessary to solve the problem, or nilifno solution exists.

The objective of the question is to write a Lisp program that solves the Missionaries and Cannibals problem using depth-first search. The program should be invoked by a function call (mac start end) where start is the current state of the problem and end is the desired goal state. The program should output the sequence of moves necessary to solve the problem, or nil if no solution exists.The Missionaries and Cannibals problem is a classic river-crossing problem where three missionaries and three cannibals must cross a river using a boat which can carry at most two people, under the constraint that, for both banks, if there are missionaries present on the bank, they cannot be outnumbered by cannibals. The boat cannot cross the river by itself with no people on board.In Lisp, we can represent the state of the problem as a list of three elements: the number of missionaries on the left bank, the number of cannibals on the left bank, and the location of the boat (0 for left bank, 1 for right bank). We can use depth-first search to explore the state space of the problem, starting from the initial state and ending at the goal state. We keep track of the path from the initial state to the current state, and if we reach the goal state, we return this path as the solution.Here is a Lisp program that implements this approach:```lisp (defun mac (start end) (let ((visited (list start)) (stack (list (list start)))) (loop while stack do (let* ((path (pop stack)) (state (first path))) (if (equal state end) (return (reverse path)) (loop for new-state in (expand state) do (unless (member new-state visited) (push new-state visited) (push (cons new-state path) stack)))))))) (defun expand (state) (let ((m (first state)) (c (second state)) (b (third state))) (loop for dm from -2 to 2 for dc from -2 to 2 when (and (>= (+ m dm) 0) (= (+ c dc) 0) (= (+ m dm) (+ c dc)) (zerop (+ m dm))) (or (>= (- 3 (+ m dm)) (- 3 (+ c dc))) (zerop (- 3 (+ m dm)))) (= b (if (or (> dm 0) (> dc 0)) 0 1))) collect (list (+ m dm) (+ c dc) (if (= b 0) 1 0))))) ```In this program, the function `mac` performs depth-first search, and the function `expand` generates all possible next states from a given state. The `mac` function maintains a stack of paths to be explored and a list of visited states. It pops a path from the stack, checks if the last state in the path is the goal state, and if not, it generates all possible next states and pushes them onto the stack. The `expand` function generates all possible next states by trying all possible moves of missionaries and cannibals, and checks if each move leads to a valid state.The Lisp program provided uses depth-first search to solve the Missionaries and Cannibals problem. It represents the state of the problem as a list of three elements and uses a stack to keep track of the path from the initial state to the current state. If the goal state is reached, the path is returned as the solution.