{"trustable":false,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv\u003e\n 多校联赛终于要结束了,永日至秦要和女朋友一起去看电影。这天,女朋友想给永日至秦一个考验,在永日至秦正准备出发的时候,女朋友告诉他,她在电影院等他,永日至秦过来的路线必须满足给定的规则:\n \u003cbr\u003e \n \u003cspan\u003e1、假设\u003c/span\u003e永日至秦在的位置是1号点,女朋友在的位置是n号点,则他们之间有n-2个点可以走,永日至秦每次走的时候只能走到比当前所在点编号大的位置;\n \u003cbr\u003e 2、永日至秦来的时候不能按一定的顺序经过某些地方。比如,如果女朋友告诉永日至秦不能经过1 -\u0026gt; 2 -\u0026gt; 3,那么就要求永日至秦来的时候走过的路径不能包含有1 -\u0026gt; 2 -\u0026gt; \n \u003cspan\u003e3这部分,但是1\u003c/span\u003e -\u0026gt; 3 \n \u003cspan\u003e或者1\u003c/span\u003e -\u0026gt; \n \u003cspan\u003e2都是可以的,这样的限制路径可能有多条。\u003c/span\u003e\n \u003cbr\u003e 这让永日至秦非常头痛,现在他把问题交给了你。\n \u003cbr\u003e \n \u003cspan\u003e特别说明,如果1\u003c/span\u003e 2 3这三个点共线,但是永日至秦是直接从1到3然后再从3继续,那么此种情况是不认为永日至秦经过了2这个点的。\n \u003cbr\u003e 现在,永日至秦即想走最短的路尽快见到女朋友,又不想打破女朋友的规定,你能帮助永日至秦解决这个问题吗?\n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e 输入包含多组样例,每组样例首先包含两个整数n和m,其中n代表有n个点,永日至秦在1号点,女朋友在n号点,m代表永日至秦的女朋友有m个要求;\u003cbr\u003e \u003cspan\u003e接下来n行每行输入2个整数x\u003c/span\u003e 和y(x和y均在int范围),代表这n个点的位置(点的编号从1到n);\u003cbr\u003e 再接着是m个要求,每个要求2行,首先一行是一个k,表示这个要求和k个点有关,然后是顺序给出的k个点编号,代表永日至秦不能走k1 -\u0026gt; \u003cspan\u003ek2\u003c/span\u003e -\u0026gt; \u003cspan\u003ek3\u003c/span\u003e ……-\u0026gt; \u003cspan\u003eki这个顺序的路径;\u003c/span\u003e\u003cbr\u003e n 和 \u003cspan\u003em等于0的时候输入结束。\u003c/span\u003e\u003cbr\u003e \u003cbr\u003e \u003cb\u003e[Technical Specification]\u003c/b\u003e\u003cbr\u003e 2 \u0026lt;\u003d n \u0026lt;\u003d 50\u003cbr\u003e 1 \u0026lt;\u003d m \u0026lt;\u003d 100\u003cbr\u003e 2 \u0026lt;\u003d k \u0026lt;\u003d 5\u003cbr\u003e \u0026nbsp;\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e 对于每个样例,如果存在满足要求的最短路径,请输出这个最短路径,结果保留两位小数;否则,请输出”Can not be reached!” \u003cspan\u003e(引号不用输出)。\u003c/span\u003e\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e\r\n3 1\r\n1 1\r\n2 1\r\n3 1\r\n2\r\n1 2\r\n\r\n2 1\r\n0 0\r\n1 1\r\n2 \r\n1 2\r\n\r\n5 3\r\n0 0\r\n5 3\r\n1 2\r\n1 22\r\n5 21\r\n3\r\n1 2 3\r\n2 \r\n4 5\r\n2\r\n1 5\r\n\r\n0 0\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e\r\n2.00\r\nCan not be reached!\r\n21.65\u003c/pre\u003e"}}]}