#pragma GCC optimize("O3") #include using namespace std; const int N = 1e6 + 10; unsigned long long has[N],base[N]; unsigned long long get(int l,int r){ if(r < l)return 0; return has[r] - has[l-1] * base[r-l+1]; } unordered_mapmp; int main(){ base[0] = 1; for(int i = 1 ; i < N ; i ++ )base[i] = base[i-1] * 131; int n,m;cin >> n >> m; vectors(n); for(int i = 0 ; i < n ; i ++ ){ cin >> s[i]; } sort(s.begin(),s.end()); s.resize(unique(s.begin(),s.end())-s.begin()); if(s.size() == 1){ return cout << (m+1) * 26,0; } string ta = s[0] + s[1][s[1].size()-1]; for(int i = 1 ; i <= m+1 ; i ++ ){ has[i] = has[i-1] * 131 + ta[i-1]; } for(int i = 1 ; i <= m+1 ; i ++ ){ mp[get(1,i-1) * 131 + get(i+1,m+1)]; } bool ok = 0; // cout << get(2,m+1) << '\n'; mp[get(1,m)] = mp[get(2,m+1)] = 1; for(int i = 0 ; i < n ; i ++ ){ ok = 0; for(int j = 1 ; j <= m ; j ++ ){ has[j] = has[j-1] * 131 + s[i][j-1]; } // cout << get(1,2) << '\n'; for(int j = 1 ; j <= m ; j ++ ){ // cout << get(j,m) << '\n'; if(mp.count(get(1,j-1) * 131 + get(j,m))){ ok = 1; break; } } if(ok == 0)break; } if(ok){ string tb = s[1][0] + s[0]; mp.clear(); for(int i = 1 ; i <= m+1 ; i ++ ){ has[i] = has[i-1] * 131 + tb[i-1]; } for(int i = 1 ; i <= m+1 ; i ++ ){ mp[get(1,i-1) * 131 + get(i+1,m+1)]; } mp[get(1,m)] = mp[get(2,m+1)] = 1; for(int i = 0 ; i < n ; i ++ ){ ok = 0; for(int j = 1 ; j <= m ; j ++ ){ has[j] = has[j-1] * 131 + s[i][j-1]; } for(int j = 1 ; j <= m ; j ++ ){ if(mp.count(get(1,j-1) * 131 + get(j,m))){ ok = 1; break; } } if(ok == 0)break; } if(ok)return cout << 2,0; } int pos1,pos2; for(int i = 0 ; i < m ; i ++ ){ pos1 = i; if(s[0][i] != s[1][i])break; } for(int i = m-1 ; i > 0 ; i -- ){ pos2 = i; if(s[0][i] != s[1][i])break; } ok = 0; for(int i = pos1 ; i < pos2 ; i ++ ){ if(s[0][i] != s[1][i+1])ok = 1; } string x; for(int i = 0 ; i < pos1 ; i ++ ){ x += s[0][i]; } string y = x; // if(!ok){ x += s[1][pos1]; for(int i = pos1 ; i < s[0].size() ; i ++ )x += s[0][i]; // } // else{ y += s[0][pos1]; for(int i = pos1 ; i < s[1].size() ; i ++ )y += s[1][i]; // } mp.clear(); for(int i = 1 ; i <= m+1 ; i ++ ){ has[i] = has[i-1] * 131 + x[i-1]; } for(int i = 1 ; i <= m+1 ; i ++ ){ mp[get(1,i-1) * 131 + get(i+1,m+1)]; } ok = 0; mp[get(1,m)] = mp[get(2,m+1)] = 1; for(int i = 0 ; i < n ; i ++ ){ ok = 0; for(int j = 1 ; j <= m ; j ++ ){ has[j] = has[j-1] * 131 + s[i][j-1]; } for(int j = 1 ; j <= m ; j ++ ){ if(mp.count(get(1,j-1) * 131 + get(j,m))){ ok = 1; break; } } if(ok == 0)break; } int res = ok; ok = 0; x = y; // cout << x << '\n'; mp.clear(); for(int i = 1 ; i <= m+1 ; i ++ ){ has[i] = has[i-1] * 131 + x[i-1]; } for(int i = 1 ; i <= m+1 ; i ++ ){ mp[get(1,i-1) * 131 + get(i+1,m+1)]; } ok = 0; mp[get(1,m)] = mp[get(2,m+1)] = 1; for(int i = 0 ; i < n ; i ++ ){ ok = 0; for(int j = 1 ; j <= m ; j ++ ){ has[j] = has[j-1] * 131 + s[i][j-1]; } for(int j = 1 ; j <= m ; j ++ ){ if(mp.count(get(1,j-1) * 131 + get(j,m))){ ok = 1; break; } } if(ok == 0)break; } res += ok; cout << res << '\n'; }