Matrix

You have a rectangular grid of size N × M, namely, there are cells (x, y) for 1 ≤ x ≤ N, 1 ≤ y ≤ M. Two cells are adjacent if they share a side. More formally, two cells (x1, y1), (x2, y2) are adjacent if |x1 − x2| + |y1 − y2| = 1. Between two adjacent cells there can be a wall. Two cells a and b are connected if there is a way between them (in other words there is a sequence of cells c1, c2, ...,