入门⏱ 1000ms💾 256MB#P2287🏷️ 图论广度优先搜索

题目描述

城市有 $N$ 个巴士站(编号 $1 \sim N$,$1$ 为起点,$N$ 为终点)和 $m$ 条 单向巴士线路:每条线路按顺序依次停靠若干站点。

换乘次数 = 乘坐的线路条数 $- 1$。求从站 $1$ 到站 $N$ 的最少换乘次数; 无法乘巴士到达输出 NO。

输入格式

第一行两个整数 $m, n$; 以下 $m$ 行,每行为一条线路按运行顺序停靠的站号列表(站号间用空格分开,行长不限)。

输出格式

一行:最少换乘次数;无法到达输出 NO。

数据范围

$$1 \le m \le 100,\ 1 < n \le 500$$

样例输入 #1
3 7
6 7
4 7 3 6
2 1 3 5
样例输出 #1
2
样例输入 #2
1 5
1 2 3 4 5
样例输出 #2
0