Roads

Time limit2sMemory limit128 MB

Summary

Choose exactly M edges from a graph on N cities so the result is connected and the sorted edge list is lexicographically smallest, or report impossible.

Level: Medium7 of 10
Topics: Greedy, Union-find, Graph, Sorting
Solved: No attempts yet

Problem

There are N cities numbered from 0 to N-1, and undirected roads connect some pairs of cities.

Each road has a priority. Consider two roads (A, B) and (C, D), where A < B and C < D. If the tuple (A, B) is lexicographically smaller than (C, D), then road (A, B) has higher priority. Lexicographic order means that at the first position where two tuples differ, the tuple with the smaller value is smaller.

A road set is written with its roads sorted from highest priority to lowest priority. Road sets are also compared lexicographically by those ordered road tuples. A road set is connected if every city can be reached from every other city using only roads in the set.

Find the highest-priority connected road set that contains exactly M roads.

Input

The first line contains N, the number of cities, and M, the required number of roads. N is a positive integer no greater than 50, and M is an integer with N-1 <= M <= 1,000.

The next N lines contain the adjacency matrix. In the i-th of these lines, the j-th character is Y if a road exists between city i and city j, and N otherwise. The matrix is symmetric, and no city is connected to itself.

Output

If no answer exists, print -1.

Otherwise, print N integers: the number of chosen roads incident to city 0, then city 1, and so on through city N-1.

Examples5

Example 1
Input
```
3 2
NYY
YNY
YYN
```
Expected output
```
2 1 1
```

Example 2

Input

5 10
NYYYY
YNYYY
YYNYY
YYYNY
YYYYN

Expected output

4 4 4 4 4

Example 3
Input
```
5 4
NYNNY
YNNNY
NNNNN
NNNNY
YYNYN
```
Expected output
```
-1
```

Example 4

Input

8 10
NYYNYYYN
YNNNNYYN
YNNNYNNN
NNNNNNYY
YNYNNNNN
YYNNNNYY
YYNYNYNY
NNNYNYYN

Expected output

5 3 2 2 2 2 3 1

Example 5
Input
```
4 5
NNYY
NNYY
YYNN
YYNN
```
Expected output
```
-1
```