7259: BZOJ3259：生日宴会

再过几天就是 Alice的生日了！Alice   决定举办一个生日宴会，并想邀请她的好朋友们参加宴会。Alice 是个很 有魅力的人，她一共有 N个好朋友。而她的这些好朋友互相之间可能认识，也可能不认识，还可能有矛盾。这N个 人之间是否认识是无所谓的，但是如果两个人之间存在矛盾就会产生一些问题。这里，矛盾关系是双向的。Alice 知道，如果她邀请的任意一个好朋友小 X在宴会上仅看到一个与小 X有矛盾的人小 Y，就会不太高兴，不过可以假 装没看见。但是，如果小 X再次看到另一个与小 X有矛盾的人小 Z，小 X就会很生气并离开宴会。为了防止这样的 情形出现， Alice 决定只邀请她的一部分好朋友参加宴会，使得对于这些人中的任意一个人，至多有一个与他（ 或她）有矛盾的人同时受到邀请。这样，就不会有人中途离开宴会了。经过调查，Alice 已经掌握了在她的 N个好 朋友中有哪些人之间存在矛盾。在保证上述原则的前提下，她希望邀请尽量多的好朋友参加宴会。请你帮助 Alice 计算出她最多邀请多少个好朋友参加这个宴会。注意，输入文件包含多组测试数据。

输入格式

第一行包含一个正整数 T，表示有 T组测试数据。接下来依次是 T组测试数据。每组测试数据的第一行包含一个正 整数 N，表示 Alice的好朋友数目。接下来 N行，每行一个长度为 N的字符串。其中第 i个字符串 Str[i]的第 j 个字符 Str[i][j]表示第i个人和第j 人是否有矛盾。若Str[i][j] = ‘Y’则表示i和j有矛盾；否则的话，Str[i] [j] = ‘N’，表示没有矛盾。数据保证对于任意 1≤i, j≤N，有 Str[i][j] = Str[j][i]；对于任意1≤i≤N， 有Str[i][i] = ‘N’

输出格式

输出 T行，每行一个整数，依次表示每组测试数据的答案。

样例输入

4 
3 
NYY
YNY 
YYN 
6 
NYYNNN 
YNYNYN 
YYNYYY 
NNYNNN 
NYYNNY 
NNYNYN 
4 
NNYN 
NNNY 
YNNN 
NYNN 
7 
NNNNNNN 
NNNNYNY 
NNNYYYY 
NNYNNYY 
NYYNNNN 
NNYYNNN 
NYYYNNN

样例输出

2 
4 
4 
5 
 
 

提示

【样例解释】 第1组数据：3个人两两之间都有矛盾，所以最多同时邀请两个人。 第2组数据：一个可行的最优方案是邀请编号为1、4、5、6的朋友。 第3组数据：每个人恰好和一个人有矛盾，因此可以邀请所有人。 第4组数据：最优方案是唯一的，即邀请编号为1、2、4、5、6的朋友。 对于 100%的数据：1≤ N≤ 40，0 ≤ M    ≤ 780   ，1≤ T ≤ 50 。

题目来源

没有写明来源