URI Online Judge | 1862

Houses of Westeros

By Ricardo Oliveira, UFPR BR Brazil

Timelimit: 1

Daenerys: "Lannister, Targaryen, Baratheon, Stark, Tyrell. They're all just spokes on a wheel."

The noble houses of Westeros are constantly fighting for the Iron Throne. To win the Game of Thrones, one must always be aware of how many houses there are in the land. It is also important to know the size of each house, since houses with many people are usually stronger than houses with fewer people.

There are N people in Westeros. For any pair of people, a spy told you whether they belong to the same house or not. If the information gathered by the spy is consistent, determine how many houses there are in Westeros, and how many people belong to each house.

Input

The first line contains an integer N (1 ≤ N ≤ 1000), the number of people. The people are numbered from 1 to N.

The next N lines contains N characters each. The j-th character in the i-th line (1 ≤ i, jN) is S if people i and j belong to the same house, or D if people i and j belong to different houses. It is guaranteed that, for all 1 ≤ i, jN, the j-th character in the i-th line is equal to the i-th character in the j-th line. Also, for all 1 ≤ iN, the i-th character in the i-th line is always S.

Output

If the information gave by the spy is inconsistent and it is not possible to determine the number of houses, print a line containing -1. Otherwise, print two lines. The first line contains an integer K, the number of houses. The second line contains K integers, the number of people in each house. The integers must be printed in non-ascending order. A space must be printed between two consecutive integers.

Input Samples Output Samples

7
SDSDDSD
DSDSSDD
SDSDDSD
DSDSSDD
DSDSSDD
SDSDDSD
DDDDDDS

3
3 3 1

4
SSDD
SSSD
DSSS
DDSS

-1