Dancing Party#1106
You are organizing a dance party. The party will be attended by boys and girls. There will be several rounds of dancing.
In each round, the guests are divided into dancing pairs. Each guest must be in exactly one pair, and each pair must contain one boy and one girl. Each boy must dance with a different girl in each round. Some boys and girls may not like each other. Each boy agrees to dance with at most girls he does not like. Similarly, each girl agrees to dance with at most boys she does not like.
You are given information for each boy and girl: whether the -th boy and -th girl (1 \le i, j \le n) like each other. Find the maximum number of dancing rounds you can organize.
The first line contains two numbers: and (1 \le n \le 50, 0 \le k \le 50). The -th character of the -th row of the matrix is 'Y' if the -th boy and the -th girl like each other, or 'N' otherwise.
Print the maximum number of dancing rounds you can organize.
Example 1
Example 2