The "Best Independent Set" problem is defined as follows: Input: An undirected graph G, in which each vertex is marked by a positive value ; and a target value T. Goal: A set of vertices S such that (a) no two vertices in S are connected by an edge in G; and (b) the total value of the vertices in S is at least T. For instance, in Graph 1 below, with T=16, there are three solutions: { C,D },{ A,E}, and {B,E} In Graph 2, with T=21 the only solution is {G,H,K} The N-Queens problem is actually a special case of this, with the vertices being the squares on the chess board, an edge between two vertices if the squares attack, all vertices have value 1 , and the target value is N. A. Describe an instance of Best Independent Set where doing a breadth-first search will construct 1000 (or more) times as many states as doing a depth-first search. B. Describe an instance of Best Independent Set where doing a depth-first search will construct 1000 (or more) times as many states as doing a breadth-first search. (Hint: There is an instance where the correct solution contains only one vertex.)