2. Pacman and Ms. Pacman are lost in an NxN maze and would like to meet; they don't care where. In each time step, both simultaneously move in one of the following directions: {NORTH, SOUTH, EAST, WEST, STOP}. They do not alternate turns. We must devise a plan which positions them together, somewhere, in as few time steps as possible. Passing each other does not count as meeting; they must occupy the same square at the same time. We can formally state this problem as a single-agent state-space search problem as follows: States: The set of pairs of positions for Pacman and Ms. Pacman, that is, {[(x1, y), (x2, y2)) | X1, X2, Y, y2 {1, 2, N}} Size of state space: N2 for both Pacmen, hence N4 total Goal test: Goal((x1, y), (x2, y2)) := (x1 = x2) and (y1 = y2) a) Determine the branching factor. (2 points) b) For each of the following graph search methods determine and explain whether it is guaranteed to output optimal solutions to this problem? (6 points) (i) DFS (ii) BFS (iii) UCS