有$n$个城市,有$m$个传送阵。第$i$个传送阵能让你$a_i$这个城市传送到$b_i$城市,注意传送阵时单向的,也就是这个传送阵不能让你从$b_i$传送回$a_i$。
你想知道从$1$号城市出发,到达其他所有的城市最少需要多少次传送,如果不可到达,输出-1
。
输入格式
第一行,一个整数$n, m$。
接下来$m$行,每行两个整数$a_i, b_i$。
输出格式
输出一行,一共$n$个整数,按顺序表示$1$号点到各个城市需要的传送次数。如果不可到达,输出-1
。
样例输入
5 5
1 2
1 4
3 2
4 5
5 1
样例输出
0 1 -1 1 2
数据规模
对于所有数据,保证$1\leq n\leq 10^5, 1\leq m\leq 2\times 10^5, 1\leq a_i, b_i \leq n$。