5. An n x n grid is an undirected graph with na vertices organized into n rows and n columns. We denote the vertex in the ith row and the jth column by (i, j). Every vertex (i, j) has exactly four neighbors (i-1,j), (i+1,j), (i, j-1), and (i, j+1), except the boundary vertices, for which i=1,i=n, j=1, or j=n. Let (x1, y), (x2, y2),...,(xm, ym) be distinct vertices, called terminals, in the nx n grid. The escape problem is to determine whether there are m vertex-disjoint paths in the grid that connect the terminals to any m distinct boundary vertices. Figure 11.10. A positive instance of the escape problem, and its solution. (a) Describe and analyze an efficient algorithm to solve the escape problem. The running time of your algorithm should be a small polynomial function of n. (b) Now suppose the input to the escape problem consists of a single integer n and the list of m terminal vertices. If m is very small, the previous running time is actually exponential in the input size! Describe and analyze an algorithm to solve the escape problem in time polynomial in m. '(c) Modify the previous algorithm to output an explicit description of the escape paths (if they exist), still in time polynomial in m. 5. An n x n grid is an undirected graph with na vertices organized into n rows and n columns. We denote the vertex in the ith row and the jth column by (i, j). Every vertex (i, j) has exactly four neighbors (i-1,j), (i+1,j), (i, j-1), and (i, j+1), except the boundary vertices, for which i=1,i=n, j=1, or j=n. Let (x1, y), (x2, y2),...,(xm, ym) be distinct vertices, called terminals, in the nx n grid. The escape problem is to determine whether there are m vertex-disjoint paths in the grid that connect the terminals to any m distinct boundary vertices. Figure 11.10. A positive instance of the escape problem, and its solution. (a) Describe and analyze an efficient algorithm to solve the escape problem. The running time of your algorithm should be a small polynomial function of n. (b) Now suppose the input to the escape problem consists of a single integer n and the list of m terminal vertices. If m is very small, the previous running time is actually exponential in the input size! Describe and analyze an algorithm to solve the escape problem in time polynomial in m. '(c) Modify the previous algorithm to output an explicit description of the escape paths (if they exist), still in time polynomial in m