信息学奥赛题库- 公交旅行

友情提示：380元/半年，儿童学编程，就上码丁实验室。

【题目描述】

在这个城市中有$n$个站台和$m$条公交线路，第$i$条公交线路由$t_i$个站台组成，记为 $s_i,1, s_i,2,…,s_i,t_i$。在$0$时刻，第$i$辆公交车会处在$s_i,1$站台，之后每个时刻公交都会到达路线中的下一个站台。当公交车到达终点站后，它下一个时刻将会回到出发的站台，注意一个站台可能在一条线路中出现多次，但不会相邻。

在$0$时刻，蒜头处在站台$1$。如果在某一时刻蒜头和公交在同一个站台，那么蒜头就可以上这辆公交车，并在任意时刻下车，上下车的过程并不会花费时间。现在蒜头想要知道，如果他只乘坐公交车出行，他分别能最早在何时到达每个站台，或是告诉他这是不可能的。

注意，蒜头一次只能乘坐一辆车，但在通往某个站台的过程中，蒜头可以乘坐许多辆不同的公交车。

【输入】

输入的第一行是两个整数$n,m$，分别表示站台和线路的个数。

接下来的$m$行，每行的第一个数为$t_i$，表示线路的长度，随后的$t_i$个整数描述一条公交线路。

【输出】

共输出$1$行$n-1$个数，第$i$个数表示到达站台$i+1$的最短时间。如果不能到达，输出$-1$。

【输入样例】

8 4
2 5 4
3 6 1 2
4 4 2 1 3
2 7 8

【输出样例】

2 3 4 6 3 -1 -1

【提示】

【数据规模】

100%的数据，$t_i≥2$。