CF160D Edges in MST

给定一个无自环无重边的连通带权无向图。 我们提醒你，图的生成树定义为该图的无环连通子图，包含所有顶点。树的权值定义为所有包含的边的权值之和。最小生成树（MST）指的是权值最小的生成树。对于任意连通图，最小生成树一定存在，但一般情况下最小生成树可能不唯一。 你的任务是对于给定图的每一条边，判断它属于以下哪种情况：是否属于所有最小生成树，是否至少属于一个最小生成树，或是否不属于任何最小生成树。

第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 10^{5}$，$n-1 \leq m \leq \min\left(\frac{n(n-1)}{2}, 2 \times 10^5\right)$），表示图的顶点数和边数。接下来的 $m$ 行每行包含三个整数 $a_i$、$b_i$、$w_i$（$1 \leq a_i, b_i \leq n, 1 \leq w_i \leq 10^6, a_i \neq b_i$），表示第 $i$ 条边连接的两个顶点编号及其权值。保证图连通、无自环、无重边。

输出 $m$ 行，每行输出一个字符串，依次表示每条边的答案。如果第 $i$ 条边属于所有最小生成树，输出 "any"；如果第 $i$ 条边至少属于一个最小生成树，输出 "at least one"；如果第 $i$ 条边不属于任何最小生成树，输出 "none"。答案顺序与输入边顺序一致。

在第二个样例中，该图的最小生成树唯一：包含前两条边。 在第三个样例中，任意两条边都能组成该图的最小生成树。这意味着每条边至少属于某一个最小生成树。 由 ChatGPT 5 翻译