题目描述

一个无线传感器网络由若干独立采集数据的设备和一个控制中心组成。每个设备必须把采集到的数据传到控制中心处理，但由于设备限制，并不是每台设备都可以与控制中心直接相连。为了解决这一问题，你将传感器网络设计成树状结构。树根为控制中心，而每台设备恰好有一个父亲节点（要么为控制中心，要么为另一台设备）。一台设备的儿子设备个数称为它的负载级别。所有设备（注意，控制中心不是设备）的负载级别的最大值称为网络的负载级别。

你的任务是让整个网络的负载级别尽量小。

输入格式

第一行包含一个整数 $N$，即设备的个数。第二行包含 $N$ 个字符，表示每台设备是否能直接连接到控制中心。以下 $N$ 行每行 $N$ 个字符，其中第 $i$ 行第 $j$ 个字符为 Y 当且仅当设备 $i$ 可以作为设备 $j$ 的儿子。如果设备 $i$ 可以作为设备 $j$ 的儿子，那么在任何合法的网络中，设备 $j$ 一定不会是设备 $i$ 的后代。换句话说，如果把这 $N$ 行看作一个有向图的邻接矩阵，该图不存在有向环。

输出格式

仅一行，包含 $N$ 个整数，即每个设备的父亲。设备按照输入顺序编号为 $0$ 至 $N-1$，控制中心用 $N$ 表示。如果有多组解，输出字典序最小解。

5
YNNYN
NNNNN
YNNNY
NNNYN
NNNNN
YNNYN

5 4 3 5 0

提示

对于 $50\%$ 的数据，$2\le N\le 6$；对于另外 $50\%$ 的数据，$N=50$。