Introduction to Artificial Intelligence We consider the Missionaries and Cannibals Problem. This problem is described as follows: 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. The objective of the problem is to find the sequence of their transfer from one bank of the river to the other using the boat sailing through the river satisfying the constrains. A state can be represented by a triple, (mcb), where m is the number of missionaries on the left, cis 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). 1. Suggest the possible operations that can be done to solve the problem (an example of operator is: MM: 2 missionaries cross the river") (1 Mark) 2. Draw the undirected graph showing all the legal states and transitions from states corresponding to all legal operations. (2 Marks) 3. Give the sequence of operations from initial to goal, if Breath First Search algorithm is used to explore the graph. (1 Marks) 4. Same as question 3, but use the Depth First Search algorithm to traverse the graph. (1 Mark)