F. Параметрическая циркуляция
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вова недавно познакомился с таким комбинаторным объектом, как циркуляция в графе. Напомним определение: пусть задан ориентированный граф $$$G = (V, E)$$$. Тогда циркуляцией $$$f$$$ называется такой набор неотрицательных действительных чисел $$$f_e$$$ ($$$e \in E$$$), что для любой вершины $$$v \in V$$$ выполняется условие консервативности

$$$$$$\sum\limits_{e \in \delta^{-}(v)} f_e = \sum\limits_{e \in \delta^{+}(v)} f_e$$$$$$

где $$$\delta^{+}(v)$$$ обозначает множество рёбер, входящих в вершину $$$v$$$, а $$$\delta^{-}(v)$$$ — множество рёбер, исходящих из вершины $$$v$$$. Иными словами, в любую вершину входит столько же потока, сколько из неё исходит.

Будем также называть допустимой $$$lr$$$-циркуляцией такую циркуляцию $$$f$$$, что для любого ребра выполнено соотношение $$$l_e \leq f_e \leq r_e$$$, где $$$l_e$$$ и $$$r_e$$$ для каждого ребра $$$e \in E$$$ это два неотрицательных действительных числа, задающих нижнюю и верхнюю границу для величины циркуляции по ребру $$$e$$$.

Вова полон исследовательского духа, а ещё он не умеет вовремя останавливаться при обдумывании новых тем, с которыми он познакомился. Сейчас он размышляет над следующим естественным вопросом — пусть граф фиксирован, а каждая величина $$$l_e$$$ и $$$r_e$$$ сама по себе является линейной функцией действительного переменного $$$t$$$:

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

Обратите внимание, переменная $$$t$$$ — общая для всех рёбер.

Предположим, что $$$t$$$ выбирается случайным образом из равномерного распределения на отрезке $$$[0, 1]$$$. Какова тогда вероятность, что в данном графе существует допустимая $$$lr$$$-циркуляция?

Входные данные

В первой строке входных данных находятся два целых числа $$$n$$$, $$$m$$$ ($$$1 \leq n \leq 1000$$$, $$$1 \leq m \leq 2000$$$).

В последующих $$$m$$$ строках даны описания рёбер графа в формате $$$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$$$), где $$$u_e$$$ и $$$v_e$$$ — соответственно начальная и конечная вершина ребра $$$e$$$, а оставшиеся 4 числа задают линейные функции для нижней и верхней границы величины циркуляции.

Гарантируется, что для любого значения $$$t \in [0, 1]$$$ и для любого ребра $$$e \in E$$$ выполнено условие $$$0 \leq l_e(t) \leq r_e(t) \leq 10^4$$$.

Выходные данные

Выведите единственное действительное число — вероятность того, что в данном графе существует допустимая $$$lr$$$-циркуляция при условии, что $$$t$$$ выбирается из равномерного распределения на отрезке $$$[0, 1]$$$. Ваш ответ будет засчитан, если его абсолютная погрешность относительно ответа жюри не превосходит $$$10^{-6}$$$.

Пример
Входные данные
3 3
1 2 0 3 -4 7
2 3 -2 5 1 6
3 1 0 4 0 4
Выходные данные
0.25
Примечание

В первом тесте из условия циркуляция из условий консервативности следует, что величина $$$f_e$$$ должна быть одинаковой по всем трём рёбрам. Вне зависимости от выбора $$$t$$$ единственное допустимое значение циркуляции по последнему ребру — это $$$4$$$, поэтому искомая вероятность есть

$$$$$$P(4 \in [3, -4t + 7]~~\&~~4 \in [-2t + 5, t + 6]) = 0.25$$$$$$