#F4. 换乘
换乘
T4 换乘(bus)
时间限制:1.0 秒 空间限制:256 MB
题目描述
某城市有 个公交站点,编号 到 ,还有 条公交线路。第 条线路经过 个站点(保证同一条线路内站点互不相同);线路是双向运行的,即对于一条线路上的任意两个站点,都可以乘坐该线路在它们之间往返,中途可以任意上下车。
你可以在任意站点换乘任意线路(前提是该站点在这条线路上)。从乘坐的一条线路换成另一条线路,称为一次「换乘」;在起点上车的第一条线路不计为换乘。
你目前位于站点 ,想要前往站点 。请你求出最少需要换乘多少次;若无论如何都无法到达站点 ,输出 。
输入格式
第一行两个正整数 。
接下来 行,每行先给出一个正整数 ,紧接着 个互不相同的整数,表示该线路经过的站点编号(站点编号在 到 之间)。
输出格式
输出一个整数:最少换乘次数;若无法到达,输出 。
样例 1
输入:
6 3
3 1 3 5
3 2 3 4
2 4 6
输出:
2
样例 1 解释: 先乘线路 1 从站点 1 到站点 3,换乘线路 2 到站点 4,再换乘线路 3 到站点 6,共换乘 2 次。可以证明没有更少的方案。
样例 2
输入:
4 2
2 1 2
2 3 4
输出:
-1
样例 2 解释: 站点 与 之间没有任何线路相连,站点 4 无法到达。
样例 3
输入:
3 1
3 1 2 3
输出:
0
样例 3 解释: 站点 1 和站点 3 都在线路 1 上,直接乘坐即可,换乘 0 次。
数据范围
对于全部测试数据:;;;;保证同一条线路内站点互不相同。