Edge Shortest Path Count in Directed Graph

An unweighted directed graph is given with \( n \) vertices and \( m \) edges. For each edge, you are to compute the total number of shortest paths between every ordered pair of distinct vertices that pass through that edge. If there are multiple shortest paths between a pair \( (A,B) \), each occurrence is counted separately.

More formally, for each edge \( e = (u,v) \), let its value be \[ \text{value}(e) = \sum_{\substack{A,B\in\{1,\ldots,n\},\\ A\neq B}} \; \#\{\text{shortest paths from } A \text{ to } B \text{ that contain } e\} \pmod{10^9+7}. \]

Note: In the event that there are multiple shortest paths between two vertices, each shortest path is counted.

Example: Consider the graph with 4 vertices and 4 edges, with the edges given (in the input order) as:

1 2
2 3
1 3
3 4

For this graph, the shortest paths (between different vertices) are:

• From 1 to 2: path 1 \to 2 uses edge 1.
• From 1 to 3: the shortest is 1 \to 3 using edge 3 (the alternative 1 \to 2 \to 3 is longer because the direct edge gives a distance of 1).
• From 1 to 4: path 1 \to 3 \to 4 uses edges 3 and 4.
• From 2 to 3: path 2 \to 3 uses edge 2.
• From 2 to 4: path 2 \to 3 \to 4 uses edges 2 and 4.
• From 3 to 4: path 3 \to 4 uses edge 4.

Thus, the answers for the edges in input order are:

• Edge 1 (1 \to 2): 1
• Edge 2 (2 \to 3): 2
• Edge 3 (1 \to 3): 2
• Edge 4 (3 \to 4): 3

Your task is to compute these counts modulo \(10^9+7\) for a given directed graph.

inputFormat

The input begins with a line containing two integers \( n \) and \( m \) \((1 \leq n \leq 500,\ 1 \leq m \leq 10^4)\), representing the number of vertices and edges respectively. The following \( m \) lines each contain two integers \( u \) and \( v \) \((1 \le u,v \le n)\), indicating a directed edge from vertex \( u \) to vertex \( v \).

outputFormat

Output exactly \( m \) lines. The \( i \)th line should contain a single integer: the number of shortest paths (over all ordered pairs of distinct vertices) that pass through the \( i \)th edge (in the input order), taken modulo \(10^9+7\).

sample

4 4
1 2
2 3
1 3
3 4

1
2
2
3