Counting Shortest Paths through Each Road

C has \(n\) cities and \(m\) unidirectional roads connecting them. A path is called a shortest path if and only if there is no other path from its start to its end with a smaller total length. Two shortest paths are considered different if and only if the sequences of roads they use are different.

Your task is to evaluate the importance of each road by computing, for every road, the number of different shortest paths that pass through it.

Note: All road lengths are 1.

Input Format: The first line contains two integers \(n\) and \(m\). Each of the following \(m\) lines contains two integers \(u\) and \(v\) (1-indexed), indicating a directed road from city \(u\) to city \(v\).

Output Format: Output \(m\) lines. The \(i\)th line should contain one integer that denotes the number of distinct shortest paths that pass through the \(i\)th road (in the input order).

inputFormat

The first line contains two positive integers \(n\) and \(m\) (the number of cities and roads, respectively).

Then \(m\) lines follow, each containing two integers \(u\) and \(v\) (1-indexed) indicating a directed road from city \(u\) to city \(v\). It is guaranteed that each road has length 1.

outputFormat

Output \(m\) lines. The \(i\)th line should output a single integer representing the number of distinct shortest paths that pass through the \(i\)th road given in the input.

sample

3 3
1 2
2 3
1 3

1
1
1