有$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$。