Write a Java program to solve the Cannibals and Missionaries problem: Three missionaries and three cannibals are on one side of a river, along with a boat that can hold one or two people. 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 place. Implement and solve this problem by generating a tree structure and then use iterative deepening search to search the tree. Once a solution is found, please output the order of the steps taken to reach the solution. For example, the output could look something like:

3M, 3C, 1 for 3 missionaries, 3 cannibals and the boat all on the 1 or starting side

3M, 2C, 0 for 3 missionaries, and 2 cannibals on the starting side and the boat is now on side 0 or the other side of the river

Continue pattern untill solution which will be 0M, 0C, 0 where everyone is on the other side including the boat