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