#include<cstdio> #include<cstring> #include<queue> #include<cmath> #include<algorithm> using namespace std; template<class T> inline void read(T &_a){ bool f=0;int _ch=getchar();_a=0; while(_ch<'0' || _ch>'9'){if(_ch=='-')f=1;_ch=getchar();} while(_ch>='0' && _ch<='9'){_a=(_a<<1)+(_a<<3)+_ch-'0';_ch=getchar();} if(f)_a=-_a; } int n,m,t[101],g[101]; bool vis[1<<11]; struct node { int a,cnt; node() {} node(int x,int y): a(x),cnt(y) {} }; queue<node>q; int main() { read(n); read(m); for (register int i=1,a;i<=m;++i) for (register int v=1;v<=n;++v) { t[i]<<=1; g[i]<<=1; read(a); if(a==1) t[i]|=1; if(a==-1) g[i]|=1; } node ff; ff.a=(1<<n)-1; vis[ff.a]=true; ff.cnt=0; q.push(ff); while(!q.empty()) { node now=q.front(); q.pop(); if(now.a==0) {printf("%d",now.cnt); return 0;} for (register int i=1;i<=m;++i) if(!vis[(now.a-(now.a&t[i]))|g[i]]) vis[(now.a-(now.a&t[i]))|g[i]]=true,q.push(node((now.a-(now.a&t[i]))|g[i],now.cnt+1)); } printf("The patient will be dead."); return 0; }