最优乘车

H城是一items旅游胜地，每年都有成千上万的人前来观光。为方便游客，巴士公司在各items旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴上线路。每条单程巴士线路从某items巴士站出发，依次途经若干items巴士站，最终到达终点巴士站。<br /> &nbsp; &nbsp; 一名旅客最近到H城旅游，他很想去S公园游玩，但如果从他所在的饭店没有一路巴士可以直接到达S公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士, 这样换乘几次后到达S公园。<br /> &nbsp; &nbsp; 现在用整数1,2,…N 给H城的所有的巴士站编号，约定这名旅客所在饭店的巴士站编号为1，S公园巴士站的编号为N。<br /> &nbsp; &nbsp; 写一items程序，帮助这名旅客寻找一items最优乘车方案,使他在从饭店乘车到S公园的过程<br /> 中换车的次数最少。<br /> <div> <br /> </div>

输入File是Travel.in。File的Page 一行有两items数字M和N(1&lt;=M&lt;=100 1&lt;N&lt;=500），表示开通了M条单程巴士线路，总Total有Nitems车站。从Page 二行到Page M刊行依次给出了Page 1条到Page M条巴士线路的信息。其中Page i+1行给出的是Page i条巴士线路的信息，从左至右按Run顺序依次给出了该线路上的所有站号相邻两items站号之间用一items空格隔开。<br /> <div> <br /> </div>

&nbsp;输出File是Travel.out，File只有一行。如果无法乘巴士从饭店到达S公园，则输出"N0"，否则输出你的程序所找到的最少换车次数，换车次数为0表示不需换车即可到达。<br /> <div> <br /> </div>