#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using Int = long long; template ostream &operator<<(ostream &os, const pair &a) { return os << "(" << a.first << ", " << a.second << ")"; }; template ostream &operator<<(ostream &os, const vector &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; } template void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; } template bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; } template bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; } namespace bm { constexpr int LIM_N0 = 100'010; constexpr int LIM_N1 = 100'010; constexpr int LIM_M = 400'010; int n0, n1, m, as[LIM_M], bs[LIM_M]; int to[LIM_N0], fr[LIM_N1], tof; int pt[LIM_N0 + 2], zu[LIM_M], used[LIM_N0], lev[LIM_N0], que[LIM_N0], *qb, *qe; void init(int n0_, int n1_) { n0 = n0_; n1 = n1_; m = 0; } int ae(int u, int v) { as[m] = u; bs[m] = v; return m++; } int augment(int u) { used[u] = tof; for (int j = pt[u]; j < pt[u + 1]; ++j) { const int v = zu[j]; const int w = fr[v]; if (!~w || (used[w] != tof && lev[u] < lev[w] && augment(w))) { to[u] = v; fr[v] = u; return 1; } } return 0; } int run() { memset(pt, 0, (n0 + 2) * sizeof(int)); for (int i = 0; i < m; ++i) ++pt[as[i] + 2]; for (int u = 2; u <= n0; ++u) pt[u + 1] += pt[u]; for (int i = 0; i < m; ++i) zu[pt[as[i] + 1]++] = bs[i]; memset(to, ~0, n0 * sizeof(int)); memset(fr, ~0, n1 * sizeof(int)); memset(used, ~0, n0 * sizeof(int)); for (tof = 0; ; ) { qb = qe = que; memset(lev, ~0, n0 * sizeof(int)); for (int u = 0; u < n0; ++u) if (!~to[u]) lev[*qe++ = u] = 0; for (; qb != qe; ) { const int u = *qb++; for (int j = pt[u]; j < pt[u + 1]; ++j) { const int w = fr[zu[j]]; if (~w && !~lev[w]) lev[*qe++ = w] = lev[u] + 1; } } int f = 0; for (int u = 0; u < n0; ++u) if (!~to[u]) f += augment(u); if (!f) return tof; tof += f; } } // s: true, t: false (s: reachable from unmatched left) // vertex cover: (0: false, 0: true) // independent set: (0: true, 1: false) bool side0[LIM_N0], side1[LIM_N1]; void dfs(int u) { if (!side0[u]) { side0[u] = true; for (int j = pt[u]; j < pt[u + 1]; ++j) { const int v = zu[j]; if (!side1[v]) { side1[v] = true; const int w = fr[v]; if (~w) dfs(w); } } } } void minCut() { memset(side0, 0, n0 * sizeof(bool)); memset(side1, 0, n1 * sizeof(bool)); for (int u = 0; u < n0; ++u) if (!~to[u]) dfs(u); } } // namespace bm char buf[100'010]; int H, W; vector S; int main() { for (; ~scanf("%d%d", &H, &W); ) { S.resize(H); for (int x = 0; x < H; ++x) { scanf("%s", buf); S[x] = buf; } int A = 0, B = 0; vector> ids(H, vector(W, -1)); for (int x = 0; x < H; ++x) for (int y = 0; y < W; ++y) { if (S[x][y] == 'r') ids[x][y] = A++; if (S[x][y] == 'h') ids[x][y] = B++; } bm::init(A, B); { int bx, by; bx = by = -1; for (int x = 0; x < H; ++x) for (int y = 0; y < W; ++y) { if (S[x][y] == 'r') if (x == bx) bm::ae(ids[x][y], ids[bx][by]); if (S[x][y] == 'h') { bx = x; by = y; } } bx = by = -1; for (int x = 0; x < H; ++x) for (int y = W; --y >= 0; ) { if (S[x][y] == 'r') if (x == bx) bm::ae(ids[x][y], ids[bx][by]); if (S[x][y] == 'h') { bx = x; by = y; } } bx = by = -1; for (int y = 0; y < W; ++y) for (int x = 0; x < H; ++x) { if (S[x][y] == 'r') if (y == by) bm::ae(ids[x][y], ids[bx][by]); if (S[x][y] == 'h') { bx = x; by = y; } } bx = by = -1; for (int y = 0; y < W; ++y) for (int x = H; --x >= 0; ) { if (S[x][y] == 'r') if (y == by) bm::ae(ids[x][y], ids[bx][by]); if (S[x][y] == 'h') { bx = x; by = y; } } } const int res = bm::run(); puts((res == A) ? "Yes" : "No"); } return 0; }