CF457E.Flow Optimality

There is a computer network consisting of n nodes numbered 1 through n. There are links in the network that connect pairs of nodes. A pair of nodes may have multiple links between them, but no node has a link to itself.

Each link supports unlimited bandwidth (in either direction), however a link may only transmit in a single direction at any given time. The cost of sending data across a link is proportional to the square of the bandwidth. Specifically, each link has a positive weight, and the cost of sending data across the link is the weight times the square of the bandwidth.

The network is connected (there is a series of links from any node to any other node), and furthermore designed to remain connected in the event of any single node failure.

You needed to send data from node 1 to node n at a bandwidth of some positive number k. That is, you wish to assign a bandwidth to each link so that the bandwidth into a node minus the bandwidth out of a node is  - k for node 1, k for node n, and 0 for all other nodes. The individual bandwidths do not need to be integers.

Wishing to minimize the total cost, you drew a diagram of the network, then gave the task to an intern to solve. The intern claimed to have solved the task and written the optimal bandwidths on your diagram, but then spilled coffee on it, rendering much of it unreadable (including parts of the original diagram, and the value of k).

From the information available, determine if the intern's solution may have been optimal. That is, determine if there exists a valid network, total bandwidth, and optimal solution which is a superset of the given information. Furthermore, determine the efficiency of the intern's solution (if possible), where efficiency is defined as total cost divided by total bandwidth.

存在一个由编号为 $1$ 到 $n$ 的 $n$ 个节点组成的计算机网络。网络中存在若干连接节点对的链路。一对节点之间可能有多条链路，但任意节点均不与自身相连。

每条链路支持无限带宽（双向），但在任意时刻仅能单向传输数据。在链路上发送数据的成本与带宽的平方成正比。具体而言，每条链路具有一个正权重，其传输成本等于该权重乘以带宽的平方。

该网络是连通的（即任意两个节点之间均存在一条链路序列），并且进一步设计为：即使任意单个节点发生故障，网络仍保持连通。

你需要以某个正数 $k$ 的带宽将数据从节点 $1$ 发送至节点 $n$。换言之，你需要为每条链路分配一个带宽值，使得对于每个节点，流入带宽减去流出带宽满足如下条件：节点 $1$ 为 $-k$，节点 $n$ 为 $k$，其余所有节点均为 $0$。各链路分配的带宽值不必为整数。

为最小化总成本，你绘制了该网络的示意图，并将该任务交由一名实习生求解。实习生声称已成功求出最优解，并将最优带宽值标注在你的示意图上；但随后不慎将咖啡洒在图上，导致图中大量信息无法辨认（包括原始示意图的部分内容以及 $k$ 的具体取值）。

根据当前可获得的信息，请判断实习生的解是否可能是最优解。即：判断是否存在某个合法的网络结构、某个总带宽值 $k > 0$，以及某个对应的最优解，使得该最优解包含了所给定（未被咖啡污损）的信息作为其子集。此外，请尽可能确定实习生解的效率（若可行），其中效率定义为总成本除以总带宽。

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.

输入的第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 200000$；$0 \leq m \leq 200000$），分别表示网络中的节点数和已知链路数。接下来是 $m$ 行，每行包含四个整数：$f$、$t$、$w$、$b$（$1 \leq f \leq n$；$1 \leq t \leq n$；$f \neq t$；$1 \leq w \leq 100$；$0 \leq b \leq 100$）。这表示节点 $f$ 与节点 $t$ 之间存在一条权重为 $w$、带宽为 $b$ 的链路，带宽方向为从 $f$ 到 $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".

如果实习生的解法一定不是最优的，则输出“BAD x”，其中 x 是输入中第一个违反解法最优性的链接。如果实习生的解法可能为最优，则输出该解法的效率（若可确定），四舍五入取整；否则输出“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.

尽管已知的权重和带宽恰好总是整数，但其余链路的权重和带宽并不限制为整数。