🧭 《哪条路一定会被选上？》🧱（MST 边分类：all / some / none）

题目背景

在 兔猫信奥学院，加菲老师带着小兔和小猫规划“最省钱公路网”。 城市之间有很多候选道路，每条道路有造价。大家知道：要把所有城市连通，最省钱的方案就是一棵 最小生成树（MST）。

但加菲老师又问了一个更“工程”的问题：

对于每一条候选道路，它到底是 一定会出现在所有最省钱方案里？ 可能出现在某些最省钱方案里？ 还是 不可能出现在任何最省钱方案里？

你的任务：对每条边进行分类。

题目描述

给定一张 无向连通图，有 $n$ 个点、$m$ 条边，第 $i$ 条边为 $(u_i, v_i, w_i)$。

对每条边输出一行分类（按输入顺序）：

• all：这条边出现在 所有 MST 中；
• some：这条边出现在 至少一棵 MST 中；
• none：这条边 不可能出现在任何 MST 中。

输入格式

第一行两个整数 $n, m$。

接下来 $m$ 行，每行三个整数 $u, v, w$ 表示一条无向边。

输出格式

输出 $m$ 行，第 $i$ 行是第 $i$ 条边的分类字符串：all / some / none。

数据范围

• $1 \le n \le 2 \times 10^5$
• $0 \le m \le 3 \times 10^5$
• $1 \le u, v \le n,\ u \ne v$
• $1 \le w \le 10^9$
• 允许重边（同一对点之间多条边）
• 保证图连通（若 $n=1$ 则 $m$ 可能为 0）

样例 1

3 3
1 2 1
2 3 1
1 3 1

some
some
some

样例 1 解释

三条边权都相同，任意选两条就能形成 MST，所以每条边都 可能在某棵 MST 中，但没有任何一条是 必选。

样例 2

4 6
1 2 1
2 3 1
3 4 1
1 4 2
1 3 2
2 4 2

all
all
all
none
none
none

样例 2 解释

三条权为 1 的边已经形成唯一最省钱连通方式（总权 3）。任何用到权为 2 的边都会更贵，因此权为 2 的边全部是 none。