Houses of Westeros
By Ricardo Oliveira, UFPR 
Brazil
By Ricardo Oliveira, UFPR Brazil
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.
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, j ≤ N) 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, j ≤ N, 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 ≤ i ≤ N, the i-th character in the i-th line is always S.
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 |
3 |
|
4 |
-1 |