Roads

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.

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.

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.