2575. Separate Connections

单点时限: 5.0 sec

内存限制: 256 MB

Partychen are analyzing a communications network with at most 18 nodes. Character in a matrix i,j (i,j both 0-based,as matrix[i][j]) denotes whether nodes i and j can communicate (‘Y’ for yes, ‘N’ for no). Assuming a node cannot communicate with two nodes at once, return the maximum number of nodes that can communicate simultaneously. If node i is communicating with node j then node j is communicating with node i.

输入格式

The first line of input gives the number of cases, N(1 ≤ N ≤ 100). N test cases follow.

In each test case,the first line is the number of nodes M(1 ≤ M ≤ 18),then there are a grid by M*M describled the matrix.

输出格式

For each test case , output the maximum number of nodes that can communicate simultaneously

样例

Input
2
5
NYYYY
YNNNN
YNNNN
YNNNN
YNNNN
5
NYYYY
YNNNN
YNNNY
YNNNY
YNYYN
Output
2
4
Hint
The first test case:
All communications must occur with node 0. Since node 0 can only communicate with 1 node at a time, the output value is 2.
The second test case:
In this setup, we can let node 0 communicate with node 1, and node 3 communicate with node 4.

64 人解决,176 人已尝试。

79 份提交通过,共有 699 份提交。

5.8 EMB 奖励。

创建: 12 年前.

修改: 3 年,7 月前.

最后提交: 3 周前.

来源: 2009 华东师范大学 研究生复试

题目标签