小w最近喜欢研究铁路图。他有一张由n个城市，m条轨道构成的铁路图。轨道是单向的，第i条轨道

连接城市ai和bi，通过这条轨道你可以从ai到bi，但不能从bi到ai。也就是说，这条轨道是单向的。

小w想知道，对于每条轨道（连接ai和bi），如果这条轨道被删去，通过图上剩余的轨道从ai到bi的最

短距离。ai到bi的距离定义为从ai出发到bi的路径上经过的轨道的数量。特别地，如果删除这条轨道后

从ai到不了bi，则从ai到bi的距离为-1。

输入格式

第一行包含两个整数n,m，表示城市数和轨道数。

接下来m行，每行两个整数ai,bi，表示第i条有向轨道。

输出格式

输出一行包含m个整数，第i个整数表示删除第i条轨道的答案。

数据范围

对于10%的数据，n<=10,m<=20

对于40%的数据，n<=1000,m<=2000

对于100%的数据，n<=1000,m<=100000

输入数据保证没有重边和自环。

输入样例

样例输入1

3 3

1 2

2 3

1 3

样例输入2

3 6

1 2

2 1

1 3

3 1

3 2

2 3

样例输入3

3 3

1 2

2 1

1 3

输出样例

样例输出1

-1 -1 2

样例输出2

2 2 2 2 2 2

样例输出3

-1 -1 -1

样例解释

对于样例1，删除1→2的轨道，1到不了2，故答案为-1。删除1→3的轨道，从1出发可以走1→2→3到

达3，故答案为2。