给您一个连接的加权无向图,没有任何循环和多条边。
让我们提醒您,图的生成树被定义为给定图的非循环连通子图,其中包括该图的所有顶点。树的权重定义为给定树包含的边的权重之和。图的最小生成树(MST)被定义为图的生成树具有最小可能的权重。对于任何连通图显然都存在最小生成树,但在一般情况下,图的最小生成树不是唯一的。
您的任务是确定给定图的每条边的以下信息:它是否包含在任何 MST 中,或至少包含在一个 MST 中,或不包含在任何 MST 中。
输入
第一行包含两个整数 n 和 m (2 ≤ n ≤ 105, $$n-1 \leq m \leq \min(10^5, \frac{n(n-1)}{2})$$) — 相应地,图的顶点和边的数量。接下来是m行,每行包含三个整数——图的边的描述为“ai bi wi”(1≤ai,bi≤n,1≤wi≤106,ai≠bi),其中ai和bi是第i条边连接的顶点数,wi是边的权重。保证图是连通的并且不包含环或多边。
输出
打印 m 行 — 所有边缘的答案。如果第i条边包含在任何MST中,则打印“any”;如果第 i 条边至少包含在一个 MST 中,则打印“至少一个”;如果第 i 条边不包含在任何 MST 中,则打印“none”。按照输入中指定边缘的顺序打印边缘的答案。
示例
输入 #1
4 5 1 2 101 1 3 100 2 3 2 2 4 2 3 4 1
输出 #1
none any at least one at least one any
输入 #2
3 3 1 2 1 2 3 1 1 3 2
输出 #2
any any none
输入 #3
3 3 1 2 1 2 3 1 1 3 1
输出 #3
at least one at least one at least one
注意
在第二个示例中,MST 对于给定图来说是唯一的:它包含两个第一边。
在第三个示例中,任意两条边形成给定图的 MST。这意味着每条边至少包含在一个 MST 中。