Parametric Circulation

Vova는 최근 그래프에서 순환이 무엇인지 배웠다. 정의를 되짚어 보자. G = (V, E)를 유향 그래프라고 하자. 순환 f는 음이 아닌 실수들의 모음 $f_e$ (e ∈ E)로, 각 정점 v ∈ V에 대해 다음 보존 조건을 만족한다.

$∑_{e ∈ \delta^{-}(v)} f_e = ∑_{e ∈ \delta^{+}(v)} f_e$

여기서 $\delta^{+}$(v)는 정점 v에서 끝나는 간선들의 집합이고, $\delta^{-}$(v)는 정점 v에서 시작하는 간선들의 집합이다. 다시 말해, 각 정점에서 유입되는 흐름의 총량은 유출되는 흐름의 총량과 같아야 한다.

lr-순환을 각 간선에 대해 $l_e$ ≤ $f_e$ ≤ $r_e$ 조건을 만족하는 순환 f라고 하자. 여기서 각 간선 e ∈ E에 대한 $l_e$와 $r_e$는 이 간선 e에서 순환 값의 하한과 상한을 나타내는 음이 아닌 두 실수이다.

Vova는 새로운 주제의 응용에 관해 생각하는 것을 멈출 수 없t다. 지금 그는 다음과 같은 자연스러운 질문을 생각하고 있다. 그래프가 고정되어 있고, 각 값 $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 ≤ n ≤ 1000, 1 ≤ m ≤ 2000)이 주어진다.

다음 m개의 각 줄에는 그래프의 간선이 $u_e$, $v_e$, $a_e$, $b_e$, $c_e$, $d_e$ (1 ≤ $u_e$, $v_e$ ≤ n, -$10^4$ ≤ $a_e$, $c_e$ ≤ $10^4$, 0 ≤ $b_e$, $d_e$ ≤ $10^4$) 형식으로 주어진다. 여기서 $u_e$와 $v_e$는 간선 e의 시작점과 끝점이고, 나머지 4개의 정수는 순환의 상한과 하한에 대한 선형 함수를 나타낸다.

임의의 t ∈ $[0, 1]$와 임의의 간선 e ∈ E에 대해 다음 조건 0 ≤ $l_e$(t) ≤ $r_e$(t) ≤ $10^4$이 성립함이 보장된다.

t가 구간 $[0, 1]$에서 균등하게 무작위로 선택될 때, 그래프에 lr-순환이 존재할 확률인 하나의 실수 정수를 출력한다. 답과 심사위원 답의 절대 오차가 10^{-6} 이하이면 정답으로 인정된다.

첫 번째 예제에서 보존 조건에 따라 세 간선 모두에서 값 $f_e$가 같은 순환만 가능하다. t가 어떻게 선택되든 마지막 간선에서 순환 값은 4여야 하므로, 확률은 다음과 같다.

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