#include #include using namespace std; #define rep(i, a, b) for(int i = a; i < (b); ++i) #define trav(a, x) for(auto& a : x) #define all(x) x.begin(), x.end() #define sz(x) (int)(x).size() typedef long long ll; typedef pair pii; typedef pair pll; typedef vector vi; typedef vector vl; typedef long double ld; const ll INF = numeric_limits::max() / 4; struct MCMF { struct edge { int from, to, rev; ll cap, cost, flow; }; int N; vector> ed; vi seen; vector dist, pi; vector par; MCMF(int N) : N(N), ed(N), seen(N), dist(N), pi(N), par(N) {} void addEdge(int from, int to, ll cap, ll cost) { if (from == to) return; ed[from].push_back(edge{ from,to,sz(ed[to]),cap,cost,0 }); ed[to].push_back(edge{ to,from,sz(ed[from])-1,0,-cost,0 }); } void path(int s) { fill(all(seen), 0); fill(all(dist), INF); dist[s] = 0; ll di; __gnu_pbds::priority_queue> q; vector its(N); q.push({ 0, s }); while (!q.empty()) { s = q.top().second; q.pop(); seen[s] = 1; di = dist[s] + pi[s]; for (edge& e : ed[s]) if (!seen[e.to]) { ll val = di - pi[e.to] + e.cost; if (e.cap - e.flow > 0 && val < dist[e.to]) { dist[e.to] = val; par[e.to] = &e; if (its[e.to] == q.end()) its[e.to] = q.push({ -dist[e.to], e.to }); else q.modify(its[e.to], { -dist[e.to], e.to }); } } } rep(i,0,N) pi[i] = min(pi[i] + dist[i], INF); } pair maxflow(int s, int t) { ll totflow = 0, totcost = 0; while (path(s), seen[t]) { ll fl = INF; for (edge* x = par[t]; x; x = par[x->from]) fl = min(fl, x->cap - x->flow); totflow += fl; for (edge* x = par[t]; x; x = par[x->from]) { x->flow += fl; ed[x->to][x->rev].flow -= fl; } } rep(i,0,N) for(edge& e : ed[i]) totcost += e.cost * e.flow; return {totflow, totcost/2}; } // If some costs can be negative, call this before maxflow: void setpi(int s) { // (otherwise, leave this out) fill(all(pi), INF); pi[s] = 0; int it = N, ch = 1; ll v; while (ch-- && it--) rep(i,0,N) if (pi[i] != INF) for (edge& e : ed[i]) if (e.cap) if ((v = pi[i] + e.cost) < pi[e.to]) pi[e.to] = v, ch = 1; assert(it >= 0); // negative cost cycle } }; int n,m,k; const int MAXN = 103; int grid[MAXN][MAXN]; int ans[MAXN][MAXN]; int now = 1; bool match(){ vi row_deg(n, 0); vi col_deg(m, 0); int col_max = 0; rep(c1,0,n){ rep(c2,0,m){ row_deg[c1] += grid[c1][c2]; col_deg[c2] += grid[c1][c2]; col_max = max(col_max, col_deg[c2]); } } int r = row_deg.back(); if(col_max > r)return 0; MCMF mcmf(n+m+2); int rl = 0; int rr = 0; rep(c1,0,n){ rl += (row_deg[c1] == r); } rep(c1,0,m){ rr += (col_deg[c1] == r); } rep(c1,0,n){ if(row_deg[c1] == r){ mcmf.addEdge(0, c1+1, 1, 0); rep(c2,0,m){ if(grid[c1][c2] == 1){ mcmf.addEdge(c1+1, c2+n+1, 1, (col_deg[c2] != r)); } } } } rep(c2,0,m){ mcmf.addEdge(c2+n+1, n+m+1, 1, 0); } pll f = mcmf.maxflow(0,n+m+1); if(f.first != rl)return 0; if(f.second != rl-rr)return 0; // unnecessary? rep(c1,0,n){ trav(e, mcmf.ed[c1+1]){ int to = e.to; if(to != 0)to -= n+1; if(e.flow > 0){ ans[c1][to] = now; grid[c1][to]--; } } } now++; return 1; } vi col_yellows, ind_c; int row_y = 0; bool comp_c(int i, int j){ return col_yellows[i] < col_yellows[j]; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; int greys = 0; vi yellows; rep(c1,0,m){ col_yellows.push_back(0); ind_c.push_back(c1); } rep(c1,0,n){ string s; cin >> s; int y = 0; rep(c2,0,m){ grid[c1][c2] = (s[c2] == 'Y'); y += grid[c1][c2]; greys += (grid[c1][c2] == 0); ans[c1][c2] = -1; if(grid[c1][c2] == 1){ col_yellows[c2]++; if(c1 == 0)row_y++; } } yellows.push_back(y); } rep(c2,0,m){ grid[n][c2] = 0; ans[n][c2] = -1; } sort(all(ind_c), comp_c); rep(c1,0,row_y){ int i = ind_c[c1]; if(col_yellows[i] >= row_y){ cout << "Bugged!\n"; return 0; } col_yellows[i]++; grid[n][i] = 1; } greys += m-row_y; rep(c1,0,m){ if(col_yellows[c1] > row_y){ cout << "Bugged!\n"; return 0; } } yellows.push_back(row_y); n++; bool fail = 0; /* rep(c1,0,n-1){ if(yellows[c1] > yellows[c1+1])fail = 1; } */ cin >> k; if(greys + yellows.back() > k)fail = 1; if(fail){ cout << "Bugged!\n"; return 0; } rep(c1,0,yellows.back()){ assert(match()); } vi ys; rep(c1,0,m){ if(ans[0][c1] != -1){ ys.push_back(ans[0][c1]); } } rep(c1,0,n){ int y = 0; // sorts the yellows so that they are not really valid. // Unless any coincide with the final word, then do nothing. vi row2; bool bad = 0; if(c1 < n-1){ rep(c2,0,m){ row2.push_back(ans[c1][c2]); if(ans[c1][c2] != -1){ row2[c2] = ys[y]; if(ys[y] == ans[n-1][c2])bad = 1; y++; } } } else{ bad = 1; } rep(c2,0,m){ if(!bad)ans[c1][c2] = row2[c2]; if(ans[c1][c2] == -1){ ans[c1][c2] = now; now++; } cout << ans[c1][c2] << " "; }cout << "\n"; } return 0; }