Instead of swapping, first imagine shifting a tile \(G_{i,j}\) to replace an adjacent cell at \((i', j')\), leaving behind an empty space (instead of a different tile). Many things can happen:
- The tile itself can be disconnected from its old group.
- The tile can become connected to a new group.
- The tile, moving away, can break up its old group into multiple parts.
- The tile, at its new location, can merge different pre-existing groups into one.

Let \(C(i, j, i', j')\) denote the number of type-\(G_{i, j}\) tiles that will be connected to \((i', j')\) after shifting \(G_{i, j}\) to \((i', j')\). We can individually compute \(C(i, j, i', j') + C(i', j', i, j)\) to get the total number of tiles cleared in a single swap \(G_{i, j} \leftrightarrow G_{i',j'}\). The challenge is doing so efficiently.

We can build a graph with a node for each tile and an edge for every pair of adjacent tiles of the same type. There will be \(V = R*C \le 9{,}000{,}000\) nodes and \(E = O(4*R*C)\) edges. We could then theoretically solve the [dynamic connectivity](https://en.wikipedia.org/wiki/Dynamic_connectivity) problem to simulate adding/removing edges for each swap, and querying connected component sizes. Actually, we would only need to delete edges (decremental connectivity), query all neighbors of the new cell, and roll back the deletion using a persistent data structure. Unfortunately, even decremental connectivity is difficult to perform efficiently on general graphs.

Instead, we can try taking advantage of the structure of the graph. If we decompose the graph into [biconnected components](https://en.wikipedia.org/wiki/Biconnected_component) (BCCs), we see that the entire graph is a forest of block-cut trees (one for each tile group) connected by bridges at cut vertices (articulation points). For example, the cut vertices of the second sample case is denoted by asterisks:

```
1 2 1 1* 1*
1* 1 2 2 1*
1 3 3* 3 1
```

When we shift \(G_{i, j}\) to a neighboring cell \((i', j')\), there are two cases:

_Case 1_: Tile \(G_{i, j}\) was not a cut vertex: All tiles of the original group will remain connected, except maybe the shifted tile itself. Then, \(C(i, j, i', j')\) can be computed by summing the sizes of groups of type \(G_{i,j}\) that are connected to \((i', j')\). Note that neighbors can be in the same group as each other, or in \(G_{i, j}\)'s original group. We'll need a way to check the connectness of two arbitrary nodes to avoid double counting.

_Case 2_: Tile \(G_{i, j}\) was a cut vertex: We'll need a way to temporarily disconnect it before calculating the group sizes connected to \((i', j')\). The number of edges for the cut vertex (a.k.a. its color) can only be \(2\) or \(3\), for if all \(4\) neighbors were filled, the swap wouldn't be possible.

\(2\)-colored cut vertex examples:
```
1 1* 1 1 1*
1* 1
```
\(3\)-colored cut vertex example:
```
1 1
1 1*
1 1
```

In the above cases, each cut vertex is always in its own BCC block, so disconnecting the node is the same as disconnecting the entire block in the block forest.

Working through examples by hand, we see that the only way for a cut vertex to *not* be in its own size-\(1\) block is as follows (left). We have a \(2\)-colored cut vertex but its block is the entire loop:
```
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1* ... 1 --> 1 1 1 1 or 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
```

In this case, the shifted tile may become connected to a different group (middle), or to its own group again (right). Here, we can skip the disconnection/rolling back and just get the total group sizes of the other \(3\) neighbors of \((i', j')\). We'll only add \(1\) if the tile did not get reconnected to its original group.

With these observations, we can obtain the answer by solving dynamic connectivity on the block forest. For each condensed block node, we'll store the number of actual nodes in the block, a.k.a. the block size. We'll need to efficiently:

- delete an edge (and undo the deletion)
- check connectivity
- query an aggregate function (here, the sum of BCC block sizes) for an entire block tree

One way is with a link-cut forest modified to handle [subtree aggregates](https://usaco.guide/adv/link-cut-tree?lang=cpp#link-cut-tree---subtrees) (full tree queries are just a special case), which can be done with [virtual subtrees](https://codeforces.com/blog/entry/67637#comment-650436). This was the intended solution, and directly supports all of the operations we need. Other approaches include persistent disjoint set union, DFS, and bookkeeping of node component sizes.

Biconnected components and cut vertices can be computed in \(\mathcal{O}(V + E)\) time using Tarjan's algorithm. For each \(C(i, j, i', j')\) calculation, we'll do a constant number of cuts, connectivity checks, and queries on the link-cut forest, taking \(\mathcal{O}(\log V)\) time among them. The overall time complexity to compute the answer across all possible swaps is therefore \(\mathcal{O}(E + V \log V)\).