Next, implement the function `mnc_graph_search` with **Graph** Search using your proposed representation described in 1.1, 1.2 and 1.3. `mnc_graph_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 to the problem as a tuple of steps following the format in Task 1.5.

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 <= c + m <= 2$, i.e. you need to have at least one person in the boat to row the boat from one side of the river to the other.

**Note:** Your implementation should fulfill these 2 criteria:

1. Returned solutions are optimal

2. Will always return False within a finite number of steps if there is no solution

## 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 can 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.

print(mnc_graph_search(2,1)) # ((2, 0), (1, 0), (1, 1))

print(mnc_graph_search(2,2)) # ((1, 1), (1, 0), (2, 0), (1, 0), (1, 1))

print(mnc_graph_search(3,3)) # ((1, 1), (1, 0), (0, 2), (0, 1), (2, 0), (1, 1), (2, 0), (0, 1), (0, 2), (1, 0), (1, 1))

print(mnc_graph_search(4, 4)) # False

* 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.