mod = 1000000007 eps = 10**-9 def main(): import sys import itertools from collections import deque import string input = sys.stdin.readline class Dinic: def __init__(self, N): self.N = N self.adj = [[] for _ in range(N + 1)] self.lv = None self.progress = None self.inf = 1 << 60 def add_edge(self, fr, to, cap): # [to, cap, rev] forward = [to, cap, None] backward = forward[2] = [fr, 0, forward] self.adj[fr].append(forward) self.adj[to].append(backward) def bfs(self, s, t): que = deque([s]) lv = [-1] * (self.N + 1) lv[s] = 0 while que: v = que.popleft() lvv = lv[v] for u, cap, _ in self.adj[v]: if cap and lv[u] == -1: que.append(u) lv[u] = lvv + 1 if u == t: break self.lv = lv def dfs(self, s, t, flow): st = deque([s]) st_f = deque([flow]) while st: v = st[-1] f = st_f[-1] if v == t: for i in range(len(st) - 1, 0, -1): p = st[i - 1] edge = self.adj[p][self.progress[p] - 1] edge[1] -= f edge[2][1] += f v = p return f if self.progress[v] == len(self.adj[v]): st.pop() st_f.pop() continue else: adj_v = self.adj[v] for i in range(self.progress[v], len(adj_v)): i = self.progress[v] self.progress[v] = i + 1 u, cap, rev = adj_v[i] if not cap or self.lv[u] != self.lv[v] + 1: continue else: st.append(u) st_f.append(min(st_f[-1], cap)) break def max_flow(self, s, t): flow = 0 while True: self.bfs(s, t) if self.lv[t] < 0: return flow self.progress = [0] * (self.N + 1) flow_new = self.dfs(s, t, self.inf) while flow_new: flow += flow_new flow_new = self.dfs(s, t, self.inf) def fall(grid): H, W = len(grid), len(grid[0]) grid_new = [] for h in range(H): if grid[h] != "." * W: grid_new.append(grid[h]) grid_new = ["." * W] * (H - len(grid_new)) + grid_new return grid_new H, W = map(int, input().split()) grid = [] for _ in range(H): grid.append(input().rstrip('\n')) grid_fallen = fall(grid) for h in range(H): for w in range(W): if grid[h][w] != grid_fallen[h][w]: print("No") exit() empty_num = 0 for h in range(H): if grid[h] == "." * W: empty_num += 1 non_empty_num = H - empty_num if W&1: cnt = 0 for h in range(H): for w in range(W): if grid[h][w] == "#": cnt += 1 if (cnt + empty_num)&1: if empty_num == 0: print("No") exit() empty_num -= 1 L = list(range(empty_num + non_empty_num)) for v in itertools.combinations(L, empty_num): grid_new = [] v = set(v) cnt = empty_num if empty_num + non_empty_num != H: cnt += 1 for i in range(empty_num + non_empty_num): if i in v: grid_new.append("#" * W) else: grid_new.append(grid[cnt]) cnt += 1 if empty_num + non_empty_num != H: grid_new = ["." * W] + grid_new grid_new_new = [["."] * W for _ in range(H)] for h in range(H): for w in range(W): grid_new_new[h][w] = grid_new[h][w] grid_new = grid_new_new block_num = 0 for h in range(H): for w in range(W): if grid_new[h][w] == "#": block_num += 1 if block_num & 1: continue block_num //= 2 D = Dinic(H * W + 2) s = H * W + 1 t = H * W + 2 dhw = [(0, 1), (0, -1), (1, 0), (-1, 0)] for h in range(H): for w in range(W): if (h + w) % 2 == 0: D.add_edge(s, h * W + w + 1, 1) else: D.add_edge(h * W + w + 1, t, 1) if grid_new[h][w] == "#" and (h + w) % 2 == 0: for dh, dw in dhw: h_new, w_new = h + dh, w + dw if 0 <= h_new < H and 0 <= w_new < W: if grid_new[h_new][w_new] == "#": D.add_edge(h * W + w + 1, h_new * W + w_new + 1, 1) flow = D.max_flow(s, t) abc = string.ascii_letters i_abc = 0 if flow == block_num: for h in range(H): for w in range(W): if (h + w) % 2 == 0: hw = h * W + w + 1 for hw_new, cap, _ in D.adj[hw]: if hw_new == s: continue if cap == 0: h_new, w_new = divmod(hw_new - 1, W) sss = abc[i_abc] if h == h_new: if w < w_new: grid_new[h][w], grid_new[h][w_new] = sss, sss else: grid_new[h][w_new], grid_new[h][w] = sss, sss else: if h < h_new: grid_new[h][w], grid_new[h_new][w] = sss, sss else: grid_new[h_new][w], grid_new[h][w] = sss, sss i_abc += 1 print("Yes") for h in range(H): print("".join(grid_new[h])) exit() print("No") if __name__ == '__main__': main()