# Hints

Define `adj_cc_count[i][j]`

to be the number of **unique** connected components that are directly connected to cell `(i, j)`

.

Can you come up with an `O(row*col)`

algorithm to populate `adj_cc_count`

?

Start a DFS from each unvisited green cell. Assign the same `cc_id`

to each cell that you encounter. Every time you start a new DFS, increment the `cc_id`

.

At the end of this process, you will have the total connected components, and also the info on which cell lies on which connected component. Using the `cc_id`

, how to compute `adj_cc_count[i][j]`

?

Insert the `cc_id`

of each of the 4 neighbors in a set. The size of the set is the number of unique connected components that are adjacent to this cell.

Now, what happens when you turn this particular cell green? How would the number of connected components change?

This cell is the link that connects those unique connected components. Hence, we can forget about the old components and combine them into one. Hence, the new connected components would be

```
new_cc_count[i][j] = old_cc_count - adj_cc_count[i][j] + 1
```

Using this info, how do you compute the expected value?

Each red cell has an equal probability `p`

of being picked. We already know the resulting connected components when a particular red cell is picked. Hence, the answer is

```
E = p*new_cc_count[i][j]
```

for each red cell. Since `p`

is fixed, you can just sum up all these values and divide by `p`

at the end. If modular divison sounds scary, use Atcoder Modint libray (See my code for implementation details).