Science!

Time limit3sMemory limit128 MB

Summary

Given a bipartite allowance graph on n people and n buttons, find the largest number of edge-disjoint perfect matchings (a maximum k-regular subgraph).

Level: Medium7 of 10
Topics: Graph, Combinatorics, Math, Implementation
Solved: No attempts yet

Problem

Welcome to Aperture Science. For the experiment we have gathered $n$ people and $n$ buttons.

In each round, every person must stand on exactly one button, and no two people may share a button — so a single round is a one-to-one assignment of people to buttons. A person may only stand on the buttons they are cleared for.

We want to repeat this as many times as possible. The one extra rule is that, across all rounds, no person may ever stand on the same button more than once. Given who is cleared for which button, determine the maximum number of rounds $k$ that can be performed.

Input

The input contains several test cases. The first line of each case contains an integer $n$ ( $2 \le n \le 80$ ), the number of people (which equals the number of buttons). Each of the next $n$ lines contains $n$ characters. If the $j$ -th character of the $i$ -th line is Y, person $i$ is allowed to stand on button $j$ ; otherwise it is N. A line containing a single 0 terminates the input.

Output

For each test case, output a single line containing $k$ : the maximum number of rounds that can be performed so that in every round each person stands on a button they are allowed to use, each button holds exactly one person, and no person ever stands on the same button in two different rounds. This value may be $0$ .

Examples5

Example 1
Input
```
3
YYY
NYY
YNY
2
YN
YN
0
```
Expected output
```
2
0
```
Example 2
Input
```
2
YY
YY
0
```
Expected output
```
2
```
Example 3
Input
```
2
YN
YN
0
```
Expected output
```
0
```
Example 4
Input
```
3
YNN
NYN
NNY
0
```
Expected output
```
1
```
Example 5
Input
```
3
YYY
YYY
YYY
0
```
Expected output
```
3
```