import random


class disjointSets:
    def __init__(self, n):
        self.parent = list(range(n))

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

    def union(self, x, y):
        self.parent[self.find(x)] = self.find(y)


def make_random_graph(nx, ny):
    vertices = [(x, y) for y in range(ny) for x in range(nx)]
    edges = [(a, b, random.randint(1, 10)) for a in vertices for b in vertices if abs(
        a[0] - b[0]) + abs(a[1] - b[1]) == 1]
    return vertices, edges


def graph_to_array(nx, ny, edges):
    maze = [['#'] * (2 * nx + 1) for _ in range(2 * ny + 1)]
    for a, b, _ in edges:
        ax, ay = a
        bx, by = b
        maze[2 * ay + 1][2 * ax + 1] = '.'
        maze[2 * by + 1][2 * bx + 1] = '.'
        maze[ay + by + 1][ax + bx + 1] = '.'
    return maze


def MSTKruskal(vertices, edges):
    ds = disjointSets(len(vertices))
    edges.sort(key=lambda x: x[2])  # sort edges by weight
    MST = []

    for edge in edges:
        u, v, _ = edge
        if ds.find(vertices.index(u)) != ds.find(vertices.index(v)):
            ds.union(vertices.index(u), vertices.index(v))
            MST.append(edge)

    return MST


def print_maze(maze):
    for row in maze:
        print(''.join(row))


def random_maze(nx, ny):
    vertices, edges = make_random_graph(nx, ny)
    MST = MSTKruskal(vertices, edges)
    maze = graph_to_array(nx, ny, MST)
    h = len(maze)
    w = len(maze[0])

    maze[1][0] = '.'  # 입구
    maze[h-2][w-1] = '.'  # 출구
    print_maze(maze)  # 미로 출력


random_maze(11, 10)
random_maze(11, 10)
random_maze(9, 7)