{"trustable":true,"prependHtml":"\u003cstyle\u003e.table {width: 100%;} .table-bordered {border: 1px solid #222; border-collapse: collapse; border-spacing: 0;} .table-bordered th { border: 1px solid #222; }.table-bordered td { border: 1px solid #222; padding: 0 5px; }\u003c/style\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e在有向图 $G$ 中,每条边的长度均为 $1$,现给定起点和终点,请你在图中找一条从起点到终点的路径,该路径满足以下条件:\u003c/p\u003e\n\u003col\u003e\u003cli\u003e路径上的所有点的出边所指向的点都直接或间接与终点连通。\u003c/li\u003e\n\u003cli\u003e在满足条件 1 的情况下使路径最短。\u003c/li\u003e\n\u003c/ol\u003e\u003cp\u003e注意:图 $G$ 中可能存在重边和自环,题目保证终点没有出边。\u003c/p\u003e\n\u003cp\u003e请你输出符合条件的路径的长度。\u003c/p\u003e\n\u003ch3\u003e输入格式\u003c/h3\u003e\n\u003cp\u003e第一行有两个用一个空格隔开的整数 $n$ 和 $m$,表示图有 $n$ 个点和 $m$ 条边。\u003c/p\u003e\n\u003cp\u003e接下来的 $m$ 行每行 $2$ 个整数 $x,y$,之间用一个空格隔开,表示有一条边从点 $x$ 指向点$y$。\u003c/p\u003e\n\u003cp\u003e最后一行有两个用一个空格隔开的整数 $s, t$,表示起点为 $s$,终点为 $t$。\u003c/p\u003e\n\u003ch3\u003e输出格式\u003c/h3\u003e\n\u003cp\u003e输出只有一行,包含一个整数,表示满足题目描述的最短路径的长度。如果这样的路径不存在,输出$-1$。\u003c/p\u003e\n\u003ch3\u003e样例一\u003c/h3\u003e\n\u003ch4\u003einput\u003c/h4\u003e\n\u003cpre\u003e3 2\n1 2\n2 1\n1 3\n\n\u003c/pre\u003e\n\n\u003ch4\u003eoutput\u003c/h4\u003e\n\u003cpre\u003e-1\n\n\u003c/pre\u003e\n\n\u003ch4\u003eexplanation\u003c/h4\u003e\n\u003cp\u003e起点$1$与终点$3$不连通,所以满足题目描述的路径不存在,故输出$-1$。\u003c/p\u003e\n\u003ch3\u003e样例二\u003c/h3\u003e\n\u003ch4\u003einput\u003c/h4\u003e\n\u003cpre\u003e6 6\n1 2\n1 3\n2 6\n2 5\n4 5\n3 4\n1 5\n\n\u003c/pre\u003e\n\n\u003ch4\u003eoutput\u003c/h4\u003e\n\u003cpre\u003e3\n\n\u003c/pre\u003e\n\n\u003ch4\u003eexplanation\u003c/h4\u003e\n\u003cp\u003e注意点$2$不能在答案路径中,因为点$2$连了一条边到点$6$,而点$6$不与终点$5$连通。\u003c/p\u003e\n\u003ch3\u003e限制与约定\u003c/h3\u003e\n\u003cp\u003e对于30%的数据,$0 \u0026lt; n \\le 10$,$0 \u0026lt; m \\le 20$;\u003c/p\u003e\n\u003cp\u003e对于60%的数据,$0 \u0026lt; n \\le 100$,$0 \u0026lt; m \\le 2000$;\u003c/p\u003e\n\u003cp\u003e对于100%的数据,$0 \u0026lt; n \\le 10000$,$ 0 \u0026lt; m \\le 200000$,$0 \u0026lt; x,y,s,t \\le n$,$ x,s \\ne t$。\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003e时间限制:\u003c/strong\u003e$1\\texttt{s}$\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003e内存限制:\u003c/strong\u003e$128\\texttt{MB}$\u003c/p\u003e\n\u003ch3\u003e下载\u003c/h3\u003e\n\u003cp\u003e\u003ca href\u003d\"https://uoj.ac/download.php?type\u003dproblem\u0026amp;id\u003d19\"\u003e样例数据下载\u003c/a\u003e\u003c/p\u003e\n"}}]}