DAG Maze Game: Expected Reward

In the final Replay after 99 Replays, Shay finally discovers that the maze is a directed acyclic graph (DAG). To ensure that the last Replay is still entertaining, Shifeng Shun arranges a little game for Shay and Risuki.

We are given a DAG (G) with (n) nodes and (m) edges. Each edge has a length of (1). For each edge (e_i) that goes from some node to a vertex (u), let (l_i) be the shortest distance from a given starting node (s) to (u). The weight of edge (i) is defined as [ w_i = p - l_i, ] where (p) is a given integer.

The game proceeds as follows (all choices are made in the order below and are public):

1. Risuki stands at node (s).
2. Shifeng Shun randomly selects a target node (t) (note that (t) can be equal to (s)).
3. If (t) is not reachable from (s), the game ends immediately.
4. Shay chooses an edge from the graph.
5. Risuki then chooses an (s\to t) path.
6. If the edge chosen by Shay appears on the path chosen by Risuki then Risuki pays Shay an amount equal to the edge’s weight, that is, (p - l_i).

Since Risuki wants to lose as little money as possible and Shay wants to maximize her income, both will act optimally. Notice that if there exists an (s\to t) path that avoids Shay’s chosen edge then Risuki will avoid that edge and pay nothing. Thus, in order for Shay to guarantee a positive payment, she must choose an edge that is present in every (s\to t) path. In other words, the edge must be a bridge for (s\to t) connectivity. Let (F(t)) be the maximum edge weight among all edges which are present in every (s\to t) path (and hence force Risuki’s hand) and if no such edge exists then we define (F(t)=0).

Your task is to compute the expected reward that Shay will receive. More precisely, since (t) is chosen uniformly at random among the (n) nodes, you must calculate [ E = \frac{1}{n}\sum_{t=1}^{n} F(t), ] where if (t) is not reachable from (s) we take (F(t)=0).

Note: The weight of an edge (e=(u,v)) is (p - d(v)) where (d(v)) is the shortest distance from (s) to (v). It can be shown that, in a DAG, an edge that is present in every (s\to t) path is exactly one that appears in the unique dominator tree of the graph (with root (s)). For each reachable node (t\neq s), let the unique path in the dominator tree from (s) to (t) be (s = v_0, v_1, \dots, v_k=t). Then we have [ F(t) = \max_{1\le i\le k} (p - d(v_i)). ]

It is guaranteed that (G) is a DAG and all edges have unit length.

inputFormat

Input Format:

The first line contains four integers (n), (m), (p) and (s) ((1\le s\le n)), where (n) is the number of nodes and (m) is the number of edges. Each of the next (m) lines contains two integers (u) and (v) representing a directed edge from (u) to (v) (edges have length 1). It is guaranteed that (G) is a directed acyclic graph (DAG).

outputFormat

Output Format:

Output a single floating point number representing the expected reward (i.e. (E)) that Shay will receive. Your answer is considered correct if its absolute or relative error does not exceed (10^{-6}).

sample

4 4 10 1
1 2
1 3
2 4
3 4

6.500000