#include using namespace std; struct dsu { public: dsu() : _n(0) {} dsu(int n) : _n(n), parent_or_size(n, -1) {} int merge(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); int x = leader(a), y = leader(b); if (x == y) return x; if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y); parent_or_size[x] += parent_or_size[y]; parent_or_size[y] = x; return x; } bool same(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); return leader(a) == leader(b); } int leader(int a) { assert(0 <= a && a < _n); if (parent_or_size[a] < 0) return a; return parent_or_size[a] = leader(parent_or_size[a]); } int size(int a) { assert(0 <= a && a < _n); return -parent_or_size[leader(a)]; } std::vector> groups() { std::vector leader_buf(_n), group_size(_n); for (int i = 0; i < _n; i++) { leader_buf[i] = leader(i); group_size[leader_buf[i]]++; } std::vector> result(_n); for (int i = 0; i < _n; i++) { result[i].reserve(group_size[i]); } for (int i = 0; i < _n; i++) { result[leader_buf[i]].push_back(i); } result.erase( std::remove_if(result.begin(), result.end(), [&](const std::vector& v) { return v.empty(); }), result.end()); return result; } private: int _n; // root node: -1 * component size // otherwise: parent std::vector parent_or_size; }; int main(){ int h, w; cin >> h >> w; vector A(h); for(auto &&s:A)cin >> s; dsu uf(h * w); auto f = [&](int y, int x){return y * w + x;}; auto g = [&](int v){return make_pair(v / w, v % w);}; for(int y = 0; y < h; y++){ for(int x = 0; x < w; x++){ if(A[y][x] == '#')continue; if(x + 1 < w && A[y][x] == A[y][x + 1])uf.merge(f(y, x), f(y, x + 1)); if(y + 1 < h && A[y][x] == A[y + 1][x])uf.merge(f(y, x), f(y + 1, x)); } } auto G = uf.groups(); int cnt = 0; vector tar; for(auto &&vec:G){ int y, x; tie(y, x) = g(vec[0]); cnt += (A[y][x] == '.'); if(A[y][x] == '.')tar = vec; } if(cnt >= 2){ cout << "NO" << endl; return 0; } vector> d={{-1,0},{0,-1},{1,0},{0,1}}; vector used(h * w); function dfs=[&](int y,int x,int s,int sy,int sx){ if(y < 0 || x < 0 || y >= h || x >= w)return false; if(A[y][x] == '#')return false; if(used[f(y, x)] && y == sy && x == sx)return (count(used.begin(), used.end(), true) == tar.size()); if(used[f(y, x)])return false; used[f(y, x)] = true; if(dfs(y + d[s].first, x + d[s].second, s, sy, sx))return true; if(dfs(y + d[(s + 1) % 4].first, x + d[(s + 1) % 4].second, (s + 1) % 4, sy, sx))return true; used[f(y, x)] = false; return false; }; for(auto &&v:tar){ int y, x; tie(y, x) = g(v); for(int i = 0; i < 4; i++){ fill(used.begin(), used.end(), false); if(dfs(y, x, i, y, x)){ cout << "YES" << endl; return 0; } } } cout << "NO" << endl; }