### 问题描述 卓儿正在 $X$ 国旅行。那里有许多城市，它们之间有一些单向道路相连。卓儿想知道关于最短路径的事情，这条路径从一个城市开始，然后又回到同一个城市。由于卓儿喜欢短途旅行，她让你找出 $X$ 国中每个城市的这样的路径长度。 ### 输入格式 第一行包含一个整数 $N$，表示城市的数量。 接下来是 $N$ 行，每行包含 $N$ 个整数 $H_{ij}$。保证 $H_{ij}$ 是 $0$ 或 $1$，$1$ 表示 $i$ 和 $j$ 之间有一条道路，$0$ 表示没有道路。 ### 输出格式 输出 $N$ 行，一行一个整数，即从城市 $i$ 开始并以城市 $i$ 结束的最短路径的长度。如果路径不存在，则打印 `NO WAY`。 ### 样例输入 ``` 5 0 1 1 1 1 1 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 ``` ### 样例输出 ``` 2 2 1 2 NO WAY ``` ### 评测数据规模 $1 \leq N \leq 1000$，$0 \leq H_{ij} \leq 1$。