CF457E Flow Optimality

在一个由 $ n $ 个节点组成的计算机网络中，这些节点的编号从 1 到 $ n $。网络中存在若干连接节点的链路，一对节点之间可能存在多条链路，但没有任意节点与自身相连。 每条链路都可以承载无限带宽（双向），但是在某一时刻只能单向传输数据。通过链路发送数据所产生的成本与带宽的平方成正比。具体而言，每条链路都有一个正的权重，数据通过链路发送的成本等于权重乘以带宽的平方。 该网络是连通的（即从任何一个节点可以通过一系列链路到达其他所有节点），并且设计成即使有一个节点失效，整个网络仍然保持连通。 现在，你需要从节点 1 向节点 $ n $ 发送带宽为某个正数 $ k $ 的数据。这意味着你需要为链路分配带宽，使得进入某个节点的带宽减去离开的带宽，在节点 1 是 $ -k $，在节点 $ n $ 是 $ k $，而在其他所有节点则是 0。个别带宽不需要是整数。 为了最小化总成本，你绘制了网络图，将任务交给一名实习生来解决。实习生声称已找到最优带宽，并将其标注在你的图上，但不幸的是他不小心洒了咖啡，导致大部分信息无法读取（包括部分原始图信息和 $ k $ 的值）。 请根据现有的信息，判断实习生的方案是否可能是最优的。也就是说，判断是否存在一个符合条件的网络及最优解，并且这些信息是当前已知信息的一个超集。此外，若可能，请计算实习生方案的效率，效率定义为总成本除以总带宽。

输入的第一行包含两个整数 $ 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 $。

如果实习生的方案绝对不是最优的，请输出 `BAD x`，其中 $ x $ 是第一个违反最优解条件的链路编号。如果实习生的方案可能是最优的，并且能确定效率，请将效率值四舍五入到最接近的整数输出，否则输出 `UNKNOWN`。 **本翻译由 AI 自动生成**

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