### Problem Statement

There are N cities numbered 0 to N-1. The j-th character of the i-th element of roads is 'Y' if there is a bidirectional road between cities i and j, and 'N' otherwise.

The road connecting cities A and B, where A < B, has a higher priority than the road connecting cities C and D, where C < D, if either A < C or (A = C and B < D). A set of roads is a list of one or more roads sorted from highest to lowest priority. A set S1 has a higher priority than set S2 if road S1[i] has a higher priority than road S2[i], where i is the earliest index at which the two sets differ. A set of roads is called connected if there's a path between any pair of cities containing only the roads from this set.

Your task is to find the connected set with the highest priority containing exactly M roads. Return a int[] where the i-th element is the number of roads in that set containing city i as an endpoint. Return an empty int[] if there is no such set.

### Constraints

-roads will contain between 1 and 50 elements, inclusive.

-M will be between N-1 and 1,000, inclusive, where N is the number of elements in roads.

-Each element of roads will contain exactly N characters 'Y' or 'N', where N is the number of elements in roads.

-For each i roads[i][i] will be equal to 'N'.

### Examples

0)

 `{"NYYYY","YNYYY","YYNYY","YYYNY","YYYYN"}` `10`
`Returns: {4, 4, 4, 4, 4 }`
1)

 `{"NYY","YNY","YYN"}` `2`
`Returns: {2, 1, 1 }`
 The set must contain roads 0-1 and 0-2.
2)

 `{"NYNNY","YNNNY","NNNNN","NNNNY","YYNYN"}` `4`
`Returns: { }`
 City 2 can not be connected to others.
3)

 `{"NYYNYYYN","YNNNNYYN","YNNNYNNN","NNNNNNYY","YNYNNNNN","YYNNNNYY","YYNYNYNY","NNNYNYYN"}` `10`
`Returns: {5, 3, 2, 2, 2, 2, 3, 1 }`
4)

 `{"NNYY","NNYY","YYNN","YYNN"}` `5`
`Returns: { }`
 There are totally 4 roads, so we can't choose 5 of them.

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10172

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13515&pm=10172

Gluk

#### Testers:

PabloGilberto , Olexiy , ivan_metelsky

#### Problem categories:

Graph Theory, Greedy