Question 1 (16 + 16 = 32 Points): Let there is an undirected graph with 10 nodes with the following edges (x-y means x and y are connected): 1-4, 1-2, 2-3, 2-8, 2-5, 2-7, 3-9, 3-10, 4-3, 5-6, 5-7, 5-8, 8-7. Now, I. Apply DFS considering 1 as the source node. If there are multiple options at any step, pick the node with smaller index. Draw the DFS tree. Also, mention all the back-edges. II. Repeat part II considering 6 as the source node. Question 2 (42 Points): Given a graph that is undirected, write a code that checks if it contains any cycle or not. Please use BFS or DFS to solve this problem. Do not use any built-in methods and your output must matches the sample input/output. Check the sample input below: Sample Input 1: Number of Nodes and Edges: 12 12 Edge Information: (0, 1), (0, 6), (0, 7), (1, 2), (1, 5), (2, 3), (2, 4), (7, 8), (7, 11), (8, 9), (8, 10), (10, 11) Output: This graph contains a cycle, and (7, 8), (7, 11), (8, 10), (10, 11) forms the cycle You must test the following three test cases with your code and attach the output. Sample Input 1: Number of Nodes and Edges: 12 12 Edge Information: (0, 1), (0, 6), (0, 7), (1, 2), (1, 5), (2, 3), (2, 4), (7, 8), (3, 4), (7, 11), (8, 9), (8, 10) Output: ??? Sample Input 2: Number of Nodes and Edges: 12 12 Edge Information: (0, 1), (0, 6), (0, 7), (1, 2), (1, 5), (4, 5), (2, 3), (2, 4), (7, 8), (7, 11), (8, 9), (8, 10) Output: ???