F. Parametric Circulationtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputVova 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_ewhere \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_eNote 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?InputThe 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.OutputPrint 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}.ExampleInput3 31 2 0 3 -4 72 3 -2 5 1 63 1 0 4 0 4Output0.25NoteIn 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 isP(4 \in [3, -4t + 7]~~\&~~4 \in [-2t + 5, t + 6]) = 0.25
Input3 31 2 0 3 -4 72 3 -2 5 1 63 1 0 4 0 4
Output0.25
['binary search', 'flows', '*3100']