AT_abc291_f [ABC291F] Teleporter and Closed off

有 $N$ 个城市，编号为城市 $1$、城市 $2$、$\ldots$、城市 $N$。 有一些不同城市之间可以通过单向传送器进行移动。对于每个城市 $i$（$1\leq i\leq N$），可以通过长度为 $M$ 的仅由 `0` 和 `1` 组成的字符串 $S_i$ 来表示城市 $i$ 通过传送器可以直接到达的城市。具体来说，对于 $1\leq j\leq N$： - 如果 $1\leq j-i\leq M$ 且 $S_i$ 的第 $j-i$ 个字符为 `1`，则可以从城市 $i$ 直接移动到城市 $j$。 - 否则，不能从城市 $i$ 直接移动到城市 $j$。 对于 $k=2,3,\ldots,N-1$，请解决以下问题： > 通过重复使用传送器，**不经过城市 $k$**，能否从城市 $1$ 移动到城市 $N$？如果可以，请输出所需传送器使用次数的最小值；如果不可以，输出 $-1$。

输入以以下格式从标准输入给出。 > $N$ $M$ > $S_1$ > $S_2$ > $\vdots$ > $S_N$

请将 $N-2$ 个整数以空格分隔输出在一行。第 $i$（$1\leq i\leq N-2$）个数为对应 $k=i+1$ 的问题答案。

## 限制条件 - $3\leq N\leq 10^5$ - $1\leq M\leq 10$ - $MN$，则 $S_i$ 的第 $j$ 个字符为 `0` - $N,M$ 为整数 ## 样例解释 1 通过传送器，每个城市可以直接到达以下城市： - 城市 $1$ 可以到达城市 $2,3$。 - 城市 $2$ 可以到达城市 $4$。 - 城市 $3$ 可以到达城市 $4,5$。 - 城市 $4$ 可以到达城市 $5$。 - 城市 $5$ 无法到达其它城市。 因此，从城市 $1$ 到城市 $5$ 的路径有： - 路径 $1$：城市 $1\to 2\to 4\to 5$ - 路径 $2$：城市 $1\to 3\to 4\to 5$ - 路径 $3$：城市 $1\to 3\to 5$ 不经过城市 $2$ 的路径有路径 $2$ 和路径 $3$，其中最少使用传送器次数的是路径 $3$，共 $2$ 次。 不经过城市 $3$ 的路径只有路径 $1$，共 $3$ 次。 不经过城市 $4$ 的路径只有路径 $3$，共 $2$ 次。 因此，依次输出 $2,3,2$。 ## 样例解释 2 从城市 $1$ 到城市 $6$ 只有一种方式：城市 $1\to 2\to 5\to 6$，因此对于 $k=2,5$，不存在不经过城市 $k$ 的路径；对于 $k=3,4$，上述方式满足条件，传送器使用次数为 $3$。 因此，依次输出 $-1,3,3,-1$。 注意，由于传送器是单向的，虽然可以从城市 $3$ 到城市 $4$，但不能从城市 $4$ 到城市 $3$，因此不能通过城市 $1\to 4\to 3\to 6$ 这样的方式移动。 由 ChatGPT 4.1 翻译