SRM 525 525

class Rumor {
public:
   int getMinimum( string knowledge, vector <string> graph )
    {
        int n=knowledge.size();
        vector<pair<int,int> > f;
        const pair<int,int> PINF(500,500);
        deque<int > q;
        int act,aw,bw,best=500;
        REP(iii,1<<n)
        {
            f.clear();
            f.resize(n,PINF);
            REP(i,n)
            {
                if(knowledge[i]=='Y')
                {
                    f[i].first=0,f[i].second=0;
                    q.push_back(i);
                }
            }
            while(q.size())
            {
                act=q.front();
                q.pop_front();
                aw=f[act].first+1;
                bw=f[act].second+1;
                if(aw==bw)
                {
                    (iii&(1<<act))?++aw:++bw;
                }
                REP(i,n)
                {
                    if(graph[act][i]=='Y' && (f[i].first>aw || f[i].second>bw))
                    {
                        f[i].first=min(f[i].first,aw);
                        f[i].second=min(f[i].second,bw);
                        q.push_back(i);
                    }
                }
            }
            int mmax=0;
            REP(i,n)
            mmax=max(mmax,max(f[i].first,f[i].second));
            if(best>mmax)
                best=mmax;
        }
        return best==500?-1:best;
   }
};