Question 3. (1 marks) Let G = (V, E) be an undirected connected graph with n nodes and m edges. In this question you are asked to orient the graph, i.e. pick one direction for each edge: an edge (u. v) can be directed either from u to v, or from v to u (but not both ways). While G is undirected, the oriented graph is directed. a. Give an algorithm that orients G such that in the oriented graph there is at most one node with no edges going into it. The worst-case running time of your algorithm should be O(m +n) when G is given by its adjacency list. Describe your algorithm in clear and precise English, analyze its running time, and ustify its correctness. For each edge (u, v) in E, your algorithm should output "u to if the edge is directed from u to v, or "v to if it is directed from v to u. b. Prove that if there is a way to orient G such that every vertex of G has least one edge going into it, then m n c. Give an algorithm that orients any connected undirected graph G with n vertices and mn edges such that every vertex of G has least one edge going into it. The worst-case running time of your algorithm should be O(m) when G is given by its adjacency list. Describe your algorithm in clear and precise English, analyze its running time, and justify its correctness. Question 3. (1 marks) Let G = (V, E) be an undirected connected graph with n nodes and m edges. In this question you are asked to orient the graph, i.e. pick one direction for each edge: an edge (u. v) can be directed either from u to v, or from v to u (but not both ways). While G is undirected, the oriented graph is directed. a. Give an algorithm that orients G such that in the oriented graph there is at most one node with no edges going into it. The worst-case running time of your algorithm should be O(m +n) when G is given by its adjacency list. Describe your algorithm in clear and precise English, analyze its running time, and ustify its correctness. For each edge (u, v) in E, your algorithm should output "u to if the edge is directed from u to v, or "v to if it is directed from v to u. b. Prove that if there is a way to orient G such that every vertex of G has least one edge going into it, then m n c. Give an algorithm that orients any connected undirected graph G with n vertices and mn edges such that every vertex of G has least one edge going into it. The worst-case running time of your algorithm should be O(m) when G is given by its adjacency list. Describe your algorithm in clear and precise English, analyze its running time, and justify its correctness