You are given some lists of `regions` where the first region of each list includes all other regions in that list.

Naturally, if a region `x` contains another region `y` then `x` is bigger than `y`. Also, by definition, a region `x` contains itself.

Given two regions: `region1` and `region2`, return _the smallest region that contains both of them_.

If you are given regions `r1`, `r2`, and `r3` such that `r1` includes `r3`, it is guaranteed there is no `r2` such that `r2` includes `r3`.

It is guaranteed the smallest region exists.

**Example 1:**

**Input:**
regions = \[\[ "Earth ", "North America ", "South America "\],
\[ "North America ", "United States ", "Canada "\],
\[ "United States ", "New York ", "Boston "\],
\[ "Canada ", "Ontario ", "Quebec "\],
\[ "South America ", "Brazil "\]\],
region1 =  "Quebec ",
region2 =  "New York "
**Output:**  "North America "

**Example 2:**

**Input:** regions = \[\[ "Earth ",  "North America ",  "South America "\],\[ "North America ",  "United States ",  "Canada "\],\[ "United States ",  "New York ",  "Boston "\],\[ "Canada ",  "Ontario ",  "Quebec "\],\[ "South America ",  "Brazil "\]\], region1 =  "Canada ", region2 =  "South America "
**Output:**  "Earth "

**Constraints:**

*   `2 <= regions.length <= 104`
*   `2 <= regions[i].length <= 20`
*   `1 <= regions[i][j].length, region1.length, region2.length <= 20`
*   `region1 != region2`
*   `regions[i][j]`, `region1`, and `region2` consist of English letters.


from collections import deque
from itertools import chain


def matrix_rank_transform(matrix):
    def neighbours(r, c):
        for i in range(m):
            if i != r:
                yield i, c
        for i in range(n):
            if i != c:
                yield r, i

    m, n = len(matrix), len(matrix[0])
    rank = [[0] * n for _ in range(m)]
    sorted_row = [0] * m
    sorted_col = [0] * n

    for bound in range(200001):
        q = deque((r, c) for r in range(m) for c in range(n) if matrix[r][c] == bound and rank[r][c] == 0)
        if not q:
            break
        while q:
            r, c = rc = q.popleft()
            potential_rank = sorted_row[r] + 1
            for row, col in neighbours(r, c):
                if matrix[row][col] <= matrix[r][c]:
                    potential_rank = max(potential_rank, rank[row][col] + (matrix[row][col] < matrix[r][c]))
            if potential_rank == sorted_col[c] + 1:
                rank[r][c] = sorted_row[r] = sorted_col[c] = potential_rank
            else:
                q.append(rc)
    return rank
