human
Deciphering Characters

Image data which are left by a mysterious syndicate were discovered. You are requested to analyze the data. The syndicate members used characters invented independently. A binary image corresponds to one character written in black ink on white paper.

Although you found many variant images that represent the same character, you discovered that you can judge whether or not two images represent the same character with the surrounding relation of connected components. We present some definitions as follows. Here, we assume that white pixels fill outside of the given image.

* White connected component : A set of white pixels connected to each other horizontally or vertically (see below).
* Black connected component : A set of black pixels connected to each other horizontally, vertically, or diagonally (see below).
* Connected component : A white or a black connected component.
* Background component : The connected component including pixels outside of the image. Any white pixels on the periphery of the image are thus included in the background component.


 |  |  | 
---|---|---|---
connected | disconnected | connected | connected
Connectedness of white pixels      | Connectedness of black pixels

Let C1 be a connected component in an image and C2 be another connected component in the same image with the opposite color. Let's think of a modified image in which colors of all pixels not included in C1 nor C2 are changed to that of C2. If neither C1 nor C2 is the background component, the color of the background component is changed to that of C2. We say that C1 surrounds C2 in the original image when pixels in C2 are not included in the background component in the modified image. (see below)


Two images represent the same character if both of the following conditions are satisfied.

* The two images have the same number of connected components.
* Let S and S' be the sets of connected components of the two images. A bijective function f : S -> S'...
 ... What is a the Python program you requested?
assistant
#Here is the Python program you requested.

from collections import deque
db = ((-1, 0), (-1, -1), (0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1))
dw = ((-1, 0), (0, -1), (1, 0), (0, 1))
def make():
    h, w = map(int, raw_input().split())
    if h == w == 0:
        return None
    P = ["."*(w+2)]+["."+raw_input()+"." for i in xrange(h)]+["."*(w+2)]
    deq = deque()
    w += 2; h += 2
    cnt = 0
    used = [[0]*w for i in xrange(h)]
    group = [None]
    for i in xrange(h):
        for j in xrange(w):
            if used[i][j]:
                continue
            cnt += 1
            c = P[i][j]
            dd = dw if c is '.' else db
            used[i][j] = cnt
            tmp = [(j, i)]
            deq.append((j, i))
            while deq:
                x, y = deq.popleft()
                for dx, dy in dd:
                    nx = x + dx; ny = y + dy
                    if 0 <= nx < w and 0 <= ny < h and not used[ny][nx] and P[ny][nx] == c:
                        used[ny][nx] = cnt
                        tmp.append((nx, ny))
                        deq.append((nx, ny))
            group.append(tmp)
    u = set()
    def dfs(num):
        result = []
        for x, y in group[num]:
            for dx, dy in dw:
                nx = x+dx; ny = y+dy
                if 0 <= nx < w and 0 <= ny < h and used[ny][nx] not in u:
                    v = used[ny][nx]
                    u.add(v)
                    result.append(dfs(v))
        return sorted(result)
    return dfs(1)
while 1:
    A = make()
    if not A:
        break
    B = make()
    if A == B:
        print "yes"
    else:
        print "no"