存在一个由编号为 1 到 n 的 n 个节点组成的计算机网络。网络中存在连接节点对的链路。一对节点之间可能有多个链接,但没有一个节点与自身有链接。
每个链路都支持无限带宽(在任一方向),但是链路在任何给定时间只能在单个方向上传输。通过链路发送数据的成本与带宽的平方成正比。具体来说,每个链路都有一个正权重,通过该链路发送数据的成本是权重乘以带宽的平方。
网络是连接的(从任何节点到任何其他节点都有一系列链路),并且还设计为在任何单个节点发生故障时保持连接。
您需要以某个正数 k 的带宽从节点 1 向节点 n 发送数据。也就是说,您希望为每个链路分配一个带宽,以便节点 1 的带宽减去节点的带宽为 - k,节点 n 为 k,所有其他节点为 0。各个带宽不需要是整数。
为了最小化总成本,您绘制了网络图,然后将任务交给实习生来解决。实习生声称已经解决了任务并在图表上写下了最佳带宽,但随后咖啡洒在了图表上,导致大部分内容无法阅读(包括原始图表的部分内容和 k 值)。
根据现有信息,确定实习生的解决方案是否是最佳的。也就是说,确定是否存在有效的网络、总带宽和作为给定信息的超集的最优解。此外,确定实习生解决方案的效率(如果可能),其中效率定义为总成本除以总带宽。
输入
输入将以两个整数 n 和 m (2 ≤ n ≤ 200000; 0 ≤ m ≤ 200000) 开始,分别表示网络中的节点数和已知链路数。接下来是 m 行,每行包含四个整数:f, t, w, b (1 ≤ f ≤ n; 1 ≤ t ≤ n; f ≠ t; 1 ≤ w ≤ 100; 0 ≤ b ≤ 100)。这表明节点 f 和 t 之间存在权重为 w 并承载 b 带宽的链路。带宽的方向是从f到t。
输出
如果实习生的解决方案肯定不是最优的,则打印“BAD x”,其中x是输入中违反解决方案最优性的第一个链接。如果实习生的解决方案可能是最优的,如果可以确定四舍五入到最接近的整数,则打印解决方案的效率,否则打印“UNKNOWN”。
示例
输入 #1
4 5 1 2 1 2 1 3 4 1 2 3 2 1 2 4 4 1 3 4 1 2
输出 #1
6
输入 #2
5 5 2 3 1 1 3 4 1 1 4 2 1 1 1 5 1 1 1 5 100 100
输出 #2
BAD 3
输入 #3
6 4 1 3 31 41 1 5 59 26 2 6 53 58 4 6 97 93
输出 #3
UNKNOWN
输入#4
7 5 1 7 2 1 2 3 1 1 4 5 1 0 6 1 10 0 1 3 1 1
输出#4
BAD 4
注意
虽然已知的权重和带宽恰好总是整数,但是剩余链路的权重和带宽不限于整数。