A9652. Flow Optimality

Input will begin with two integers $n$ and $m$ ( $2<=n<=200000$ ; $0<=m<=200000$ ), the number of nodes and number of known links in the network, respectively. Following this are $m$ lines with four integers each: $f$ , $t$ , $w$ , $b$ ( $1<=f<=n; 1<=t<=n; f≠t; 1<=w<=100; 0<=b<=100$ ). This indicates there is a link between nodes $f$ and $t$ with weight $w$ and carrying $b$ bandwidth. The direction of bandwidth is from $f$ to $t$ .

If the intern's solution is definitely not optimal, print "BAD $x$ ", where $x$ is the first link in the input that violates the optimality of the solution. If the intern's solution may be optimal, print the efficiency of the solution if it can be determined rounded to the nearest integer, otherwise print "UNKNOWN".

Although the known weights and bandwidths happen to always be integers, the weights and bandwidths of the remaining links are not restricted to integers.

Although the known weights and bandwidths happen to always be integers, the weights and bandwidths of the remaining links are not restricted to integers.