e-olymp
Соревнования

ADA Classes - Depth First Search

Зарплата в корпорации

Вы работаете менеджером в большой корпорации. Каждый работник может иметь несколько прямых менеджеров и несколько непосредственных подчиненных. Его подчиненные, в свою очередь, также могут иметь своих подчиненных. А его прямые менеджеры могут иметь своих менеджеров. Будем говорить, что x является боссом y, если существует такая последовательность работников a, b, ..., d, что x является менеджером a, a является менеджером b и так далее, а d является менеджером y (если x является прямым менеджером y, то x является боссом y). Если a является боссом b, то b не может быть боссом a. Согласно новой политике корпорации зарплата работника, не имеющего подчиненных, равна 1. Иначе зарплата работника равна сумме зарплат всех его подчиненных.

Вам заданы отношения между работниками. Необходмо найти зарплату всех работников.

Входные данные

Содержит несколько тестов. Первая строка каждого теста содержит количество работников n (n50). В следующих n строках заданы отношения между работниками: j-ый символ i-го элемента равен 'Y', если работник i является прямым менеджером работника j, и 'N' иначе.

Выходные данные

Для каждого теста вывести в отдельной строке суммарную зарплату всех работников.

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
1
N
4
NNYN
NNYN
NNNN
NYYN
6
NNNNNN
YNYNNY
YNNNNY
NNNNNN
YNYNNN
YNNYNN
Выходные данные #1
1
5
17