{"problem":{"name":"Teleporter Setting","description":{"content":"There are $N$ towns numbered Town $1$, Town $2$, $\\ldots$, Town $N$.   There are also $M$ _Teleporters_, each of which connects two towns bidirectionally so that a person can travel from one to the ot","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc257_f"},"statements":[{"statement_type":"Markdown","content":"There are $N$ towns numbered Town $1$, Town $2$, $\\ldots$, Town $N$.  \nThere are also $M$ _Teleporters_, each of which connects two towns bidirectionally so that a person can travel from one to the other in one minute.\nThe $i$\\-th Teleporter connects Town $U_i$ and Town $V_i$ bidirectionally. However, for some of the Teleporters, one of the towns it connects is undetermined; $U_i=0$ means that one of the towns the $i$\\-th Teleporter connects is Town $V_i$, but the other end is undetermined.\nFor $i=1,2,\\ldots,N$, answer the following question.\n\n> When the Teleporters with undetermined ends are all determined to be connected to Town $i$, how many minutes is required at minimum to travel from Town $1$ to Town $N$? If it is impossible to travel from Towns $1$ to $N$ using Teleporters only, print $-1$ instead.\n\n## Constraints\n\n*   $2 \\leq N \\leq 3\\times 10^5$\n*   $1\\leq M\\leq 3\\times 10^5$\n*   $0\\leq U_i<V_i\\leq N$\n*   If $i \\neq j$, then $(U_i,V_i)\\neq (U_j,V_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$U_1$ $V_1$\n$U_2$ $V_2$\n$\\vdots$\n$U_M$ $V_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc257_f","tags":[],"sample_group":[["3 2\n0 2\n1 2","\\-1 -1 2\n\nWhen the Teleporters with an undetermined end are all determined to be connected to Town $1$,  \nthe $1$\\-st and the $2$\\-nd Teleporters both connect Towns $1$ and $2$. Then, it is impossible to travel from Town $1$ to Town $3$.\nWhen the Teleporters with an undetermined end are all determined to be connected to Town $2$,  \nthe $1$\\-st Teleporter connects Town $2$ and itself, and the $2$\\-nd one connects Towns $1$ and $2$. Again, it is impossible to travel from Town $1$ to Town $3$.\nWhen the Teleporters with an undetermined end are all determined to be connected to Town $3$,  \nthe $1$\\-st Teleporter connects Town $3$ and Town $2$, and the $2$\\-nd one connects Towns $1$ and $2$. In this case, we can travel from Town $1$ to Town $3$ in two minutes.\n\n*   Use the $2$\\-nd Teleporter to travel from Town $1$ to Town $2$.\n*   Use the $1$\\-st Teleporter to travel from Town $2$ to Town $3$.\n\nTherefore, $-1,-1$, and $2$ should be printed in this order.\nNote that, depending on which town the Teleporters with an undetermined end are connected to, there may be a Teleporter that connects a town and itself, or multiple Teleporters that connect the same pair of towns."],["5 5\n1 2\n1 3\n3 4\n4 5\n0 2","3 3 3 3 2"]],"created_at":"2026-03-03 11:01:14"}}