← 返回题目列表

Codeforces · 160/D

D. MST 中的边缘

中文机器翻译题面 查看原题

给您一个连接的加权无向图,没有任何循环和多条边。

让我们提醒您,图的生成树被定义为给定图的非循环连通子图,其中包括该图的所有顶点。树的权重定义为给定树包含的边的权重之和。图的最小生成树(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 中。