Metro Network Passenger Flow

OItown has a network of underground metro lines designed by the famous urban planner L.Serenade. Each metro line connects two castles bidirectionally. The lines, although they may cross each other underground, provide connectivity throughout the city. Every morning, each resident travels from their home castle to their work castle via the metro network, always choosing a route with the minimum number of transfers. Here, a transfer is counted each time a resident changes from one metro line to another – note that taking a single direct metro line implies zero transfers. In the event that there are several equally optimal routes (i.e. with the same minimal number of transfers), the resident chooses one of them uniformly at random.

Your task is to determine, for each metro line, the average number of passengers (expected flow) that use that line in the morning.

You are given the complete design of the metro network and the home and work castles for each resident. It is guaranteed that the network is connected, and for any pair of castles, the number of optimal (minimal-transfer) routes is no more than \(2^{63} - 1\).

inputFormat

The input begins with two integers \(n\) and \(m\) (\(1 \le n \le 10^5\), \(1 \le m \le 10^5\)) representing the number of castles and the number of metro lines respectively. The castles are numbered from 1 to \(n\). Each of the next \(m\) lines contains two integers \(u\) and \(v\) (\(1 \le u, v \le n,\ u \neq v\)) indicating that there is a bidirectional metro line connecting castle \(u\) and castle \(v\).

The next line contains an integer \(k\) (\(1 \le k \le 10^5\)), denoting the number of residents. Each of the following \(k\) lines contains two integers \(s\) and \(t\) (\(1 \le s, t \le n\)) indicating that a resident travels from castle \(s\) (home) to castle \(t\) (work) each morning.

outputFormat

Output exactly \(m\) lines. The \(i\)-th line should contain a floating point number rounded to 6 decimal places, which is the average (expected) number of residents using the \(i\)-th metro line (in the order given in the input) in the morning.

sample

3 3
1 2
2 3
1 3
2
1 3
2 3

0.000000
1.000000
1.000000