{"problem":{"name":"Teleporter and Closed off","description":{"content":"There are $N$ cities numbered city $1$, city $2$, $\\ldots$, and city $N$.   There are also one-way teleporters that send you to different cities. Whether a teleporter can send you directly from city $","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc291_f"},"statements":[{"statement_type":"Markdown","content":"There are $N$ cities numbered city $1$, city $2$, $\\ldots$, and city $N$.  \nThere are also one-way teleporters that send you to different cities. Whether a teleporter can send you directly from city $i$ $(1\\leq i\\leq N)$ to another is represented by a length-$M$ string $S_i$ consisting of `0` and `1`. Specifically, for $1\\leq j\\leq N$,\n\n*   if $1\\leq j-i\\leq M$ and the $(j-i)$\\-th character of $S_i$ is `1`, then a teleporter can send you directly from city $i$ to city $j$;\n*   otherwise, it cannot send you directly from city $i$ to city $j$.\n\nSolve the following problem for $k=2,3,\\ldots, N-1$:\n\n> Can you travel from city $1$ to city $N$ **without visiting city $k$** by repeatedly using a teleporter? If you can, print the minimum number of times you need to use a teleporter; otherwise, print $-1$.\n\n## Constraints\n\n*   $3 \\leq N \\leq 10^5$\n*   $1\\leq M\\leq 10$\n*   $M<N$\n*   $S_i$ is a string of length $M$ consisting of `0` and `1`.\n*   If $i+j>N$, then the $j$\\-th character of $S_i$ is `0`.\n*   $N$ and $M$ are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n$S_1$\n$S_2$\n$\\vdots$\n$S_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc291_f","tags":[],"sample_group":[["5 2\n11\n01\n11\n10\n00","2 3 2\n\nA teleporter sends you\n\n*   from city $1$ to cities $2$ and $3$;\n*   from city $2$ to city $4$;\n*   from city $3$ to cities $4$ and $5$;\n*   from city $4$ to city $5$; and\n*   from city $5$ to nowhere.\n\nTherefore, there are three paths to travel from city $1$ to city $5$:\n\n*   path $1$ : city $1$ $\\to$ city $2$ $\\to$ city $4$ $\\to$ city $5$;\n*   path $2$ : city $1$ $\\to$ city $3$ $\\to$ city $4$ $\\to$ city $5$; and\n*   path $3$ : city $1$ $\\to$ city $3$ $\\to$ city $5$.\n\nAmong these paths,\n\n*   two paths, path $2$ and path $3$, do not visit city $2$. Among them, path $3$ requires the minimum number of teleporter uses (twice).\n*   Path $1$ is the only path without city $3$. It requires using a teleporter three times.\n*   Path $3$ is the only path without city $4$. It requires using a teleporter twice.\n\nThus, $2$, $3$, and $2$, separated by spaces, should be printed."],["6 3\n101\n001\n101\n000\n100\n000","\\-1 3 3 -1\n\nThe only path from city $1$ to city $6$ is city $1$ $\\to$ city $2$ $\\to$ city $5$ $\\to$ city $6$.  \nFor $k=2,5$, there is no way to travel from city $1$ to city $6$ without visiting city $k$.  \nFor $k=3,4$, the path above satisfies the condition; it requires using a teleporter three times.\nThus, $-1$, $3$, $3$, and $-1$, separated by spaces, should be printed.\nNote that a teleporter is one-way; a teleporter can send you from city $3$ to city $4$, but not from city $4$ to city $3$,  \nso the following path, for example, is invalid: city $1$ $\\to$ city $4$ $\\to$ city $3$ $\\to$ city $6$."]],"created_at":"2026-03-03 11:01:14"}}