Problem 2 [20 points]. Consider the graphs on the right, which we denote as a cycle and an in- finite diamond strip (IDS). The cycle has n nodes vi, ,Un-to that are consecutively ordered, ie., ti has th-1 and vi+1 mod n as its two neigh- bors, with vi-1 before vitl mod n. The IDS extends infinitely to both left and right. For any node in the IDS, assume that in its adjacency list, the neighbors on the left appear before the neighbors on the right. Now consider running BFS and DFS tree and graph searches on these two graphs. For the 1skn. For the diamond strip, the distance between ri (i.e., the green node) and rg (i.e, the red node) is 2m. For each of the eight search combinations, provide your estimate (i notation) of the number of nodes that has been added to the queue when the search is complete. If you think that the search does not end, the answer should be infinity. Briefly justify your answer cycle graph, suppose the start node is v and the goal node is ro .e, in big O)