Missionaries and Cannibals is a problem in which 3 missionaries and 3 cannibals want to cross from the left bank of a river to the right bank of the river. There is a boat on the left bank, but it only carries at most two people at a time (and can never cross with zero people). If cannibals ever outnumber missionaries on either bank, the cannibals will eat the missionaries. A state can be represented by a triple, (m c b), where m is the number of missionaries on the left, c is the number of cannibals on the left, and b indicates whether the boat is on the left bank or right bank. For example, the initial state is (3 3 L) and the goal state is (0 0 R). |

Operators are:

MM: 2 missionaries cross the river
CC: 2 cannibals cross the river
MC: 1 missionary and 1 cannibal cross the river
M: 1 missionary crosses the river
C: 1 cannibal crosses the river

Trace the solution to the following problem (show search and the write down the final path) using the following search algorithms:

a. Breadth-first Search
b. Depth-first Search