class DisjointSet:
    def __init__(self, n):
        self.f = list(range(n))

    def find(self, x):
        if x == self.f[x]: return x
        self.f[x] = self.find(self.f[x])
        return self.f[x]

    def merge(self, x, y):
        self.f[self.find(x)] = self.find(y)

class Solution:
    def hasValidPath(self, grid: List[List[int]]) -> bool:
        m, n = len(grid), len(grid[0])
        ds = Solution.DisjointSet(m * n)

        def getId(x, y):
            return x * n + y

        def detectL(x, y):
            if y - 1 >= 0 and grid[x][y - 1] in [1, 4, 6]:
                ds.merge(getId(x, y), getId(x, y - 1))

        def detectR(x, y):
            if y + 1 < n and grid[x][y + 1] in [1, 3, 5]:
                ds.merge(getId(x, y), getId(x, y + 1))

        def detectU(x, y):
            if x - 1 >= 0 and grid[x - 1][y] in [2, 3, 4]:
                ds.merge(getId(x, y), getId(x - 1, y))

        def detectD(x, y):
            if x + 1 < m and grid[x + 1][y] in [2, 5, 6]:
                ds.merge(getId(x, y), getId(x + 1, y))

        for x in range(m):
            for y in range(n):
                val = grid[x][y]
                if val == 1:
                    detectL(x, y); detectR(x, y)
                elif val == 2:
                    detectU(x, y); detectD(x, y)
                elif val == 3:
                    detectL(x, y); detectD(x, y)
                elif val == 4:
                    detectR(x, y); detectD(x, y)
                elif val == 5:
                    detectL(x, y); detectU(x, y)
                else:
                    detectR(x, y); detectU(x, y)

        return ds.find(getId(0, 0)) == ds.find(getId(m - 1, n - 1))