Implement tree search with dfs or bfs, works on testcase

Missionaries and Cannibals The Missionaries and Cannibals (MnC) problem is a classic river-crossing logic puzzle. It is not difficult to solve this problem by hand when we have 3 Missionaries and 3 Cannibals. However, the solution becomes less obvious when we generalize the problem to m Missionaries and c Cannibals where m and c are some positive integers. The Missionaries and Cannibals problem is usually stated as follows: m missionaries and c cannibals are on the right side of a river, along with a boat that car hold at most 2 people. Your goal is to find a way to get everyone to the other side, without ever leaving a group of missionaries in one place outnumbered by the cannibals in that location (or the missionaries will get eaten!). You can try it here: https://javalab.org/en/boat puzzle en/ to test your understanding of the problem. Some important points to note when solving this question: - If the number of missionaries is zero, it does not matter how many cannibals there are even though technically they outnumber the number of missionaries. - You need to have at least 1 person in the boat to row the boat from one side of the river to the other. - At all times, both sides of the river AND the boat must have either 0 missionaries or at least as many missionaries as cannibals. Implement the function mnc_tree_search with Tree Search using your proposed representation described in Tasks 1.1,1.2 and 1.3. mnc_tree_search takes two integers m and c, which are the numbers of missionaries and cannibals on one side of the river initially, and returns the solution to the problem as a tuple of steps. Each step is a tuple of two numbers m and c, indicating the number of missionaries and cannibals on the boat respectively as the boat moves from one side of the river to another. The odd steps are for the boat moving from right to left and the even steps are for the boat moving from left to right. Note that 1= no. of cannibals) - Step 3: 1 cannibal and 1 missionary row the boat to the RHS of the river - End: 2 missionaries and 1 cannibal are on the RHS of the river Hence, the solution is ((2,0),(1,0),(1,1))