#include #include using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 1000000000 int main(){ int V; cin>>V; long long D; cin>>D; if(D>Inf){ D = Inf + (D&1); D -= 10; } vector S(V); rep(i,V)cin>>S[i]; if(V==1){ cout<<"No"< remain(V); rep(i,V){ remain[i] = i; } mt19937 rnd(chrono::duration_cast(chrono::high_resolution_clock::now().time_since_epoch()).count()); auto start = chrono::system_clock::now(); while(remain.size()>0){ if(chrono::duration_cast(chrono::system_clock::now() - start).count() > 2800){ break; } int ind = rnd() % remain.size(); vector d(V*2,Inf); queue Q; Q.push(remain[ind]*2); while(Q.size()>0){ int u = Q.front()>>1; int b = Q.front()&1; Q.pop(); rep(i,V){ if(S[u][i]=='0')continue; int v = i; int nb = b^1; if(d[v*2+nb]!=Inf)continue; int t = d[u*2+b]; if(t==Inf)t = 0; d[v*2+nb] = t+1; Q.push(v*2+nb); } } vector ok(V,false); ok[remain[ind]] = true; bool f = true; rep(i,V){ if(d[i*2+(D&1)]>D){ f=false; break; } } if(!f)break; rep(i,V){ bool F = true; rep(j,V){ bool F2 = false; rep(k,2){ int x = i*2 + k,y = j*2 + (k^(D&1)); if(d[x]+d[y]<=D){ F2 = true; break; } } if(!F2){ F=false; break; } } if(F)ok[i] = true; } vector nr; rep(i,remain.size()){ if(!ok[remain[i]])nr.push_back(remain[i]); } swap(remain,nr); } if(remain.size()==0)cout<<"Yes"<