1 Go analysis (13 marks) In this task, we will solve a simple problem related to the ancient board game Go. The gameplay itself, while fascinating, is not relevant to this task. In the game of Go, the board is a graph. Typically this graph is a square grid, where the intersec- tions correspond to vertices, but it can be played on any arbitrary graph, and for this question we will not restrict ourselves to the square grid. Each vertex of the graph may be empty, or may have a black or white stone placed on it. We will refer to these vertices as being coloured black or white. A chain is a set of vertices where . All the vertices in the set are coloured black, or all the vertices in the set are coloured white . There is a path from each vertex in the set to each other vertex in the set which only passes through vertices in the set . No vertex in the set is adjacent to any vertex of the same colour which is not in the set Intuitively, a chain is a bunch of vertices which are all the same colour, form one big clump and is maximal (i.e. if you have 4 stones in a row, we don't say that 3 of them form a chain, we need to include all four). Chains can be captured or free. A chain is free if there is at least one empty vertex adjacent to some vertex in the chain. A chain is captured if it is not free. In this task, you will write an function captured_chains (vfile, efile), which finds all cap- tured chains present in a particular state of a Go game. Note If you know the rules of Go/how to play, please note that the input positions may not be possible states of a Go game, see the example for one such possibility. 1.1 Input the input to this function are the two files, vfile and efile, in the format described in Section D. The property value of each vertex corresponds to the colour of that vertex, as follows: . 0: empty vertex . 1: vertex coloured black . 2: vertex coloured white 1.2 Output The output of captured_chains () is a list of lists. The number of internal lists is equal to the number of captured chains in the input graph. Each list corresponds to a different chain. Each 5interior list contains the vertex IDs of all the vertices in the captured chain to which it corre- sponds (in no particular order). The interior lists may also be in any order. If there are no captured chains, then captured_chains () returns an empty list. 1.3 Example vfile ONANNNA efile 6Visual representation of the input (Intersections correspond to vertices) 0 8 Output [[O] , [1, 2, 5]] (the two lists, and the 1,2,5 in the second list, can be in any order) 1.4 Complexity captured_chains must run in O( V + E) where . V is the number of vertices in the input graph . E is the number of edges in the input graph 7