{"problem":{"name":"Blocked Roads","description":{"content":"You are given a directed graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ through $N$, and the edges are numbered $1$ through $M$. Edge $i$ $(1 \\leq i \\leq M)$ goes from Vertex $s_","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc218_f"},"statements":[{"statement_type":"Markdown","content":"You are given a directed graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ through $N$, and the edges are numbered $1$ through $M$. Edge $i$ $(1 \\leq i \\leq M)$ goes from Vertex $s_i$ to Vertex $t_i$ and has a length of $1$.\nFor each $i$ $(1 \\leq i \\leq M)$, find the shortest distance from Vertex $1$ to Vertex $N$ when all edges except Edge $i$ are passable, or print `-1` if Vertex $N$ is unreachable from Vertex $1$.\n\n## Constraints\n\n*   $2 \\leq N \\leq 400$\n*   $1 \\leq M \\leq N(N-1)$\n*   $1 \\leq s_i,t_i \\leq N$\n*   $s_i \\neq t_i$\n*   $(s_i,t_i) \\neq (s_j,t_j)$ $(i \\neq j)$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$s_1$ $t_1$\n$s_2$ $t_2$\n$\\vdots$\n$s_M$ $t_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc218_f","tags":[],"sample_group":[["3 3\n1 2\n1 3\n2 3","1\n2\n1"],["4 4\n1 2\n2 3\n2 4\n3 4","\\-1\n2\n3\n2\n\nVertex $N$ is unreachable from Vertex $1$ when all edges except Edge $1$ are passable, so the corresponding line contains `-1`."],["5 10\n1 2\n1 4\n1 5\n2 1\n2 3\n3 1\n3 2\n3 5\n4 2\n4 3","1\n1\n3\n1\n1\n1\n1\n1\n1\n1"],["4 1\n1 2","\\-1"]],"created_at":"2026-03-03 11:01:14"}}