/*#pragma GCC optimize("Ofast") #pragma GCC optimize("avx2") #pragma GCC optimize("unroll-loops")*/ #define ll int #include using namespace std; const ll MAXN=1e1+5,INF=LLONG_MAX; ll n,m,K,a[11],k2,d[11][32769],cnt[32769]; vector > v[11]; bool f[11][32769]; ll convert(string s){ ll ans=0,k=1; for(ll i=0;i0){ ans+=k%2; k/=2; } return ans; } void solve(){ cin>>n>>m>>K; string in; for(ll i=1;i<=n;++i){ cin>>in; a[i]=convert(in); } ll p,q; for(ll i=0;i>p>>q>>in; v[p].push_back({q,convert(in)}); v[q].push_back({p,convert(in)}); } k2=1; for(ll i=0;i > > s; s.insert({0,{-1,0}}); ll k,td,tm,nd,ans; while(!s.empty()){ k=-s.begin()->second.first; td=s.begin()->first; tm=s.begin()->second.second; if(k==n){ans=td; break;} s.erase(s.begin()); if(f[k][tm]==1) continue; f[k][tm]=1; d[k][tm]=td; for(auto ch : v[k]){ for(ll i=0;i=d[ch.first][i]) continue; if((i&ch.second)>=ch.second && (i&tm)>=tm && ((tm|a[k])&i)>=i){ d[ch.first][i]=nd; s.insert({nd,{-ch.first,i}}); } } } } cout<>t; while(t--) solve(); return 0; }