(a) [15 points] Construct a graph search problem with no more than 10 nodes for which all of the following are true: i. Least-cost search returns an optimal solution. ii. Depth-first search returns the highest-cost solution. iii. Breadth-first search returns a solution whose cost is strictly less than the highest-cost solution and strictly more than the least-cost solution. Note that this means your search problem must have at least 3 solutions of differing costs. Be sure to list the start and goal node(s), all edge costs and all edge directions (if your graph is directed). Draw the graph as well. (b) [5 points] List the paths in the frontier at each step of a depth first search of the problem you specified in part (1a). Also, highlight the path that will be removed from the frontier in that step. Stop when the path removed ends in a goal state. (c) [5 points] List the paths in the frontier at each step of a breadth first search of the problem you specified in part (1a). Also, highlight the path that will be removed from the frontier in that step. Stop when the path removed ends in a goal state. (d) [5 points] List the paths in the frontier at each step of a least cost search of the problem you specified in part (1a). Also, highlight the path that will be removed from the frontier in that step. Stop when the path removed ends in a goal state.