#!/usr/bin/python3 def hopcroft_karp(graph, n, m, U = None, V = None): """ Maximum bipartite matching using Hopcroft-Karp algorithm, running in O(|E| sqrt(|V|)) U and V are sets of nodes that prioritized to be part of matching. """ assert (n == len(graph)) if U == None and V == None: match1 = [-1] * n match2 = [-1] * m else: # Get initial matching from solving sub-problem of max-matching U with V # Note: uses the fact that augmentations will never remove a node from a matching graph2 = [[v for v in graph[u] if v in V] if u in U else [] for u in range(n)] match1, match2 = hopcroft_karp(graph2, n, m) # Find a greedy match for possible speed up for node in range(n): if match1[node] == -1: for nei in graph[node]: if match2[nei] == -1: match1[node] = nei match2[nei] = node break while 1: bfs = [node for node in range(n) if match1[node] == -1] depth = [-1] * n for node in bfs: depth[node] = 0 for node in bfs: for nei in graph[node]: next_node = match2[nei] if next_node == -1: break if depth[next_node] == -1: depth[next_node] = depth[node] + 1 bfs.append(next_node) else: continue break else: break pointer = [len(c) for c in graph] dfs = [node for node in range(n) if depth[node] == 0] while dfs: node = dfs[-1] while pointer[node]: pointer[node] -= 1 nei = graph[node][pointer[node]] next_node = match2[nei] if next_node == -1: # Augmenting path found while nei != -1: node = dfs.pop() match2[nei], match1[node], nei = node, nei, match1[node] break elif depth[node] + 1 == depth[next_node]: dfs.append(next_node) break else: dfs.pop() return match1, match2 n,m = [int(x) for x in input().split()] mat = [[+(c == 'Y') for c in input()] for _ in range(n)] k = sum(mat[0]) # Add extra line with k yellows using columns with fewest yellows last_row = [0] * m deg2 = [sum(mat[i][j] for i in range(n)) for j in range(m)] for j in sorted(range(m), key = deg2.__getitem__)[:k]: last_row[j] = 1 deg2[j] += 1 mat.append(last_row) n += 1 if max(deg2) > k: print('Bugged!') exit() sigma = int(input()) letters = 0 ans = [[-1] * m for _ in range(n)] for _ in range(k): graph = [[] for _ in range(n)] deg2 = [0] * m for i in range(n): for j in range(m): if mat[i][j] and ans[i][j] == -1: graph[i].append(j) deg2[j] += 1 U = set(range(n)) V = {v for v in range(m) if deg2[v] == k} k -= 1 match1, _ = hopcroft_karp(graph, n, m, U, V) for i in range(n): j = match1[i] ans[i][j] = letters letters += 1 for i in range(n): for j in range(m): if ans[i][j] == -1: ans[i][j] = letters letters += 1 if letters > sigma: print('Bugged!') exit() for row in ans: print(*[a + 1 for a in row])