## #1572 Separate Connections

34  5 s   128 MB

## Description

You are analyzing a communications network with at most 18 nodes. Assuming a node cannot communicate with two nodes at once, compute the maximum number of nodes that can communicate simultaneously.

## Input

Input consists of several test cases.

The first line of each test cases contains a positive integer N, the number of nodes in the communication network. The following N lines contain exactly N character per line and describe a matrix mat. j-th Character in i-th row of mat denotes whether nodes i and j can communicate ('Y' for yes, 'N' for no). You may assume that if node s is communicating with node t then node t is communicating with node s. i-th character of i-th row will be always 'N'.

Note that 1 ≤ N ≤ 18 for all test cases. Input is terminated by EOF.

## Output

For each test case, write a single line which gives the maximum number of nodes that can communicate simultaneously.

### Sample Output

5
NYYYY
YNNNN
YNNNY
YNNNY
YNYYN
4