题目描述

$N$ 個の都市があり、都市 $1$, 都市 $2$, $\ldots$, 都市 $N$ と番号づけられています。
いくつかの異なる都市の間は一方通行のテレポーターによって移動できます。 都市 $i$ $(1\leq\ i\leq\ N)$ からテレポーターによって直接移動できる都市は 0 と 1 からなる長さ $M$ の文字列 $S_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$ に対する問題の答えを出力せよ。

题目大意

有 $N$ 个城市，编号为 $1,2,\dots,N$。还有单向传送门，可以将你传送到不同的城市。一个传送门是否可以直接从城市 $i$ $(1\le i\le N)$ 传送到另一个城市，由长度为 $M$ 的字符串 $S_i$ 表示。具体来说，对于 $1\le j\le N$，如果 $1\le j-i\le M$ 并且 $S_i$ 的第 $(j-i)$ 个字符是1，则传送门可以直接从城市 $i$ 传送到城市 $j$；否则，它不能直接从城市 $i$ 传送到城市 $j$。对于 $k=2,3,\dots,N-1$，解决以下问题： 你能否在不经过城市 $k$ 的情况下从城市 $1$ 到达城市 $N$，反复使用传送门？如果可以，打印出你需要使用传送门的最小次数；否则，打印出 $-1$。

5 2
11
01
11
10
00

2 3 2

6 3
101
001
101
000
100
000

-1 3 3 -1

提示

制約

• $3\ \leq\ N\ \leq\ 10^5$
• $1\leq\ M\leq\ 10$
• $M\ <\ N$
• $S_i$ は 0 と 1 のみからなる長さ $M$ の文字列
• $i+j\ >\ N$ ならば $S_i$ の $j$ 文字目は 0
• $N,M$ は整数

Sample Explanation 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$ の $3$ つがあり、 - 都市 $2$ を通らない経路は経路 $2$, 経路 $3$ の $2$つであり、そのうちテレポーターの使用回数が最小となるのは経路 $3$ で、この時 $2$ 回使用する。 - 都市 $3$ を通らない経路は経路 $1$ のみであり、この時テレポーターは $3$ 回使用する。 - 都市 $4$ を通らない経路は経路 $3$ のみであり、この時テレポーターは $2$ 回使用する。 となります。よって、$2,3,2$ をこの順に空白区切りで出力します。

Sample Explanation 2

都市 $1$ から都市 $6$ へ移動する方法は、都市 $1$ $\to$ 都市 $2$ $\to$ 都市 $5$ $\to$ 都市 $6$ のみであるため、 $k=2,5$ の場合には都市 $k$ を通らずに都市 $1$ から都市 $6$ へ移動する方法は存在せず、 $k=3,4$ の場合には上の方法が条件をみたし、テレポーターを $3$ 回使用します。 よって、$-1,3,3,-1$ をこの順に空白区切りで出力します。 テレポーターは一方通行であるため、 都市 $3$ から都市 $4$ へはテレポーターによって移動できますが、 都市 $4$ から都市 $3$ へは移動できず、 都市 $1$ $\to$ 都市 $4$ $\to$ 都市 $3$ $\to$ 都市 $6$ のような移動はできない事に注意してください。