{"raw_statement":[{"iden":"problem statement","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$."},{"iden":"constraints","content":"*   $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."},{"iden":"input","content":"Input 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$"},{"iden":"sample input 1","content":"3 3\n1 2\n1 3\n2 3"},{"iden":"sample output 1","content":"1\n2\n1"},{"iden":"sample input 2","content":"4 4\n1 2\n2 3\n2 4\n3 4"},{"iden":"sample output 2","content":"\\-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`."},{"iden":"sample input 3","content":"5 10\n1 2\n1 4\n1 5\n2 1\n2 3\n3 1\n3 2\n3 5\n4 2\n4 3"},{"iden":"sample output 3","content":"1\n1\n3\n1\n1\n1\n1\n1\n1\n1"},{"iden":"sample input 4","content":"4 1\n1 2"},{"iden":"sample output 4","content":"\\-1"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}