Description

小w最近喜欢研究铁路图。他有一张由\(n\)个城市，\(m\)条轨道构成的铁路图。轨道是单向的，第\(i\)条轨道连接城市\(a_i\)和\(b_i\)，通过这条轨道你可以从\(a_i\)到\(b_i\)，但不能从\(b_i\)到\(a_i\)。也就是说，这条轨道是单向的。
小w想知道，对于每条轨道（连接\(a_i\)和\(b_i\)），如果这条轨道被删去，通过图上剩余的轨道从\(a_i\)到\(b_i\)的最短距离。\(a_i\)到\(b_i\)的距离定义为从\(a_i\)出发到\(b_i\)的路径上经过的轨道的数量。特别地，如果删除这条轨道后从\(a_i\)到不了\(b_i\)，则从\(a_i\)到\(b_i\)的距离为\(-1\)。

Format

Input

第一行包含两个整数\(n\),\(m\)，表示城市数和轨道数。
接下来m行，每行两个整数\(a_i\),\(b_i\)，表示第\(i\)条有向轨道。

Output

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

Sample 1

Input

3 3
1 2
2 3
1 3 

Output

-1 -1 2 

Sample 2

Input

3 6
1 2
2 1
1 3
3 1
3 2
2 3 

Output

2 2 2 2 2 2 

Sample 3

Input

3 3
1 2
2 1
1 3 

Output

-1 -1 -1 

Limitation

3s, 512MiB for each test case.

Hint

样例解释

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

数据范围

对于10%的数据，\(n \leq 10\) , \(m \leq 20\)
对于40%的数据，\(n \leq 1000\) , \(m \leq 2000\)
对于100%的数据，\(n \leq 1000\) , \(m \leq 100000\)

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

Source

csp2019模拟题二