CF925F Parametric Circulation

Vova has recently learned what a circulaton in a graph is. Recall the definition: let $ G = (V, E) $ be a directed graph. A circulation $ f $ is such a collection of non-negative real numbers $ f_e $ ( $ e \in E $ ), that for each vertex $ v \in V $ the following conservation condition holds: $ $$$\sum\limits_{e \in \delta^{-}(v)} f_e = \sum\limits_{e \in \delta^{+}(v)} f_e $ $

where $ \\delta^{+}(v) $ is the set of edges that end in the vertex $ v $ , and $ \\delta^{-}(v) $ is the set of edges that start in the vertex $ v $ . In other words, for each vertex the total incoming flow should be equal to the total outcoming flow.

Let a $ lr $ -circulation be such a circulation $ f $ that for each edge the condition $ l\_e \\leq f\_e \\leq r\_e $ holds, where $ l\_e $ and $ r\_e $ for each edge $ e \\in E $ are two non-negative real numbers denoting the lower and upper bounds on the value of the circulation on this edge $ e $ .

Vova can't stop thinking about applications of a new topic. Right now he thinks about the following natural question: let the graph be fixed, and each value $ l\_e $ and $ r\_e $ be a linear function of a real variable $ t $ :

$ $ l_e(t) = a_e t + b_e $ $ $ $ r_e(t) = c_e t + d_e $ $

Note that $ t $ is the same for all edges.

Let $ t $ be chosen at random from uniform distribution on a segment $ \[0, 1\] $ . What is the probability of existence of $ lr$$$-circulation in the graph?

The first line contains two integers $ n $ , $ m $ ( $ 1 \leq n \leq 1000 $ , $ 1 \leq m \leq 2000 $ ). Each of the next $ m $ lines describes edges of the graph in the format $ u_e $ , $ v_e $ , $ a_e $ , $ b_e $ , $ c_e $ , $ d_e $ ( $ 1 \leq u_e, v_e \leq n $ , $ -10^4 \leq a_e, c_e \leq 10^4 $ , $ 0 \leq b_e, d_e \leq 10^4 $ ), where $ u_e $ and $ v_e $ are the startpoint and the endpoint of the edge $ e $ , and the remaining 4 integers describe the linear functions for the upper and lower bound of circulation. It is guaranteed that for any $ t \in [0, 1] $ and for any edge $ e \in E $ the following condition holds $ 0 \leq l_e(t) \leq r_e(t) \leq 10^4 $ .

Print a single real integer — the probability of existence of $ lr $ -circulation in the graph, given that $ t $ is chosen uniformly at random from the segment $ [0, 1] $ . Your answer is considered correct if its absolute difference from jury's answer is not greater than $ 10^{-6} $ .

In the first example the conservation condition allows only circulations with equal values $ f_e $ for all three edges. The value of circulation on the last edge should be $ 4 $ whatever $ t $ is chosen, so the probability is $ $$$P(4 \in [3, -4t + 7]~~\&~~4 \in [-2t + 5, t + 6]) = 0.25 $ $$$