#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
using namespace std;
typedef long long LL;
typedef long double LD;
typedef complex<LD> CMP;
class ScotlandYard { public:
int maxMoves(vector <string> taxi, vector <string> bus, vector <string> metro)
{
const int N = taxi.size();
vector<LL> n[3];
for(int i=0; i<N; ++i) {
LL n0=0, n1=0, n2=0;
for(int k=0; k<N; ++k) {
if(taxi[i][k]=='Y')
n0 |= 1LL << k;
if(bus[i][k]=='Y')
n1 |= 1LL << k;
if(metro[i][k]=='Y')
n2 |= 1LL << k;
}
n[0].push_back(n0);
n[1].push_back(n1);
n[2].push_back(n2);
}
set<LL> vis;
try {
return rec((1LL<<N)-1, n, vis);
} catch(...) {
return -1;
}
}
int rec(LL cur, const vector<LL> n_tbl[3], set<LL>& vis)
{
if((cur & (cur-1)) == 0)
return 0;
if(!vis.insert(cur).second)
throw "infinite!";
LL next[] = {0,0,0};
for(int i=0; (1LL<<i)<=cur; ++i)
if(cur & (1LL<<i)) {
next[0] |= n_tbl[0][i];
next[1] |= n_tbl[1][i];
next[2] |= n_tbl[2][i];
}
int r0 = next[0] ? rec(next[0], n_tbl, vis)+1 : 0;
int r1 = next[1] ? rec(next[1], n_tbl, vis)+1 : 0;
int r2 = next[2] ? rec(next[2], n_tbl, vis)+1 : 0;
vis.erase(cur);
return max(r0, max(r1, r2));
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, ScotlandYard().maxMoves(taxi, bus, metro));}
int main(){
CASE(0)
string taxi_[] = {"NYN",
"NNY",
"NNN"};
vector <string> taxi(taxi_, taxi_+sizeof(taxi_)/sizeof(*taxi_));
string bus_[] = {"NNN",
"NNN",
"NNN"};
vector <string> bus(bus_, bus_+sizeof(bus_)/sizeof(*bus_));
string metro_[] = {"NNN",
"NNN",
"NNN"};
vector <string> metro(metro_, metro_+sizeof(metro_)/sizeof(*metro_));
int _ = 2;
END
CASE(1)
string taxi_[] = {"NYY",
"NNN",
"NNN"};
vector <string> taxi(taxi_, taxi_+sizeof(taxi_)/sizeof(*taxi_));
string bus_[] = {"NNN",
"NNN",
"NNN"};
vector <string> bus(bus_, bus_+sizeof(bus_)/sizeof(*bus_));
string metro_[] = {"NNN",
"NNN",
"NNN"};
vector <string> metro(metro_, metro_+sizeof(metro_)/sizeof(*metro_));
int _ = 1;
END
CASE(2)
string taxi_[] = {"NYYY",
"YNYY",
"YYNY",
"YYYN"};
vector <string> taxi(taxi_, taxi_+sizeof(taxi_)/sizeof(*taxi_));
string bus_[] = {"NNNN",
"NNNN",
"NNNN",
"NNNN"};
vector <string> bus(bus_, bus_+sizeof(bus_)/sizeof(*bus_));
string metro_[] = {"NNNN",
"NNNN",
"NNNN",
"NNNN"};
vector <string> metro(metro_, metro_+sizeof(metro_)/sizeof(*metro_));
int _ = -1;
END
CASE(3)
string taxi_[] = {"NNY",
"NNY",
"NNN"};
vector <string> taxi(taxi_, taxi_+sizeof(taxi_)/sizeof(*taxi_));
string bus_[] = {"NYN",
"NNY",
"NNN"};
vector <string> bus(bus_, bus_+sizeof(bus_)/sizeof(*bus_));
string metro_[] = {"NNN",
"NNN",
"YNN"};
vector <string> metro(metro_, metro_+sizeof(metro_)/sizeof(*metro_));
int _ = 2;
END
CASE(4)
string taxi_[] = {"NNN",
"YNY",
"NNN"};
vector <string> taxi(taxi_, taxi_+sizeof(taxi_)/sizeof(*taxi_));
string bus_[] = {"NNN",
"YNN",
"YNN"};
vector <string> bus(bus_, bus_+sizeof(bus_)/sizeof(*bus_));
string metro_[] = {"NNN",
"NNN",
"YYN"};
vector <string> metro(metro_, metro_+sizeof(metro_)/sizeof(*metro_));
int _ = -1;
END
CASE(5)
string taxi_[] = {"NNNNYNNNYY",
"NNYNNYYYYY",
"NNNNNNNNNN",
"YYNNYYNNNY",
"NNYNNNNNNN",
"YNYNYNNNYN",
"NNYNYNNNYN",
"NNNNNNYNNN",
"NNNNNNNNNN",
"NNNNNNYNNN"};
vector <string> taxi(taxi_, taxi_+sizeof(taxi_)/sizeof(*taxi_));
string bus_[] = {"NNYNNNYNNY",
"YNYNNYYNYY",
"NNNNNNNNNN",
"YNYNNYNYNY",
"NNYNNNNNYN",
"YNYNYNYNYN",
"NNYNNNNNNY",
"YNYNNNNNNN",
"NNNNNNNNNN",
"NNYNYNNNNN"};
vector <string> bus(bus_, bus_+sizeof(bus_)/sizeof(*bus_));
string metro_[] = {"NNNNNNNYNN",
"YNYNNNNNYN",
"NNNNNNNNNN",
"NYNNYNNNYY",
"NNYNNNNNNN",
"YNYNNNNNYY",
"NNNNYNNNYN",
"NNYNNNYNNN",
"NNNNNNNNNY",
"NNYNYNNNNN"};
vector <string> metro(metro_, metro_+sizeof(metro_)/sizeof(*metro_));
int _ = 21;
END
CASE(6)
string taxi_[] = {
"NYYNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"YNYNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNYNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNYNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNYNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNYNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNYNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNYNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNYNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNYNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNYNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNYNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNYNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNYNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNYNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNYNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNYNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNYNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNYNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNYNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNYNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNYNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNYNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNYNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNYNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNYNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNYNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNYN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNY",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
};
vector <string> taxi(taxi_, taxi_+sizeof(taxi_)/sizeof(*taxi_));
string bus_[] = {
"NYNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"YNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNYNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNYNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNYNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNYNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNYNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNYNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNYNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNYNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNYNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNYNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNYNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNYNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNYNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNYNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNYNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNYNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNYNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNYNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNYNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNYNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNYNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNYNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNYNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNYNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNYNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNYN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNY",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
};
vector <string> bus(bus_, bus_+sizeof(bus_)/sizeof(*bus_));
string metro_[] = {
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
};
vector <string> metro(metro_, metro_+sizeof(metro_)/sizeof(*metro_));
int _ = -1;
END
/*
CASE(7)
string taxi_[] = ;
vector <string> taxi(taxi_, taxi_+sizeof(taxi_)/sizeof(*taxi_));
string bus_[] = ;
vector <string> bus(bus_, bus_+sizeof(bus_)/sizeof(*bus_));
string metro_[] = ;
vector <string> metro(metro_, metro_+sizeof(metro_)/sizeof(*metro_));
int _ = ;
END
*/
}
// END CUT HERE