CF160D.Edges in MST

You are given a connected weighted undirected graph without any loops and multiple edges.

Let us remind you that a graph's spanning tree is defined as an acyclic connected subgraph of the given graph that includes all of the graph's vertexes. The weight of a tree is defined as the sum of weights of the edges that the given tree contains. The minimum spanning tree (MST) of a graph is defined as the graph's spanning tree having the minimum possible weight. For any connected graph obviously exists the minimum spanning tree, but in the general case, a graph's minimum spanning tree is not unique.

Your task is to determine the following for each edge of the given graph: whether it is either included in any MST, or included at least in one MST, or not included in any MST.

给你一个连通的、带权的无向图，该图不含自环和重边。

我们提醒你：图的一个生成树被定义为该图的一个无环连通子图，且包含图中的所有顶点。一棵树的权值被定义为该树所包含的所有边的权值之和。图的最小生成树（MST）被定义为该图的所有生成树中权值最小者。对于任意连通图，最小生成树显然存在；但在一般情况下，一个图的最小生成树并不唯一。

你的任务是：对给定图中的每一条边，判断它属于以下三类中的哪一类：

• 属于每一个最小生成树；
• 至少属于某一个最小生成树（但并非所有最小生成树都包含它）；
• 不属于任何最小生成树。

The first line contains two integers n and m (2 ≤ n ≤ 105, ) — the number of the graph's vertexes and edges, correspondingly. Then follow m lines, each of them contains three integers — the description of the graph's edges as "a__i b__i w__i" (1 ≤ a__i, b__i ≤ n, 1 ≤ w__i ≤ 106, a__i ≠ b__i), where a__i and b__i are the numbers of vertexes connected by the i-th edge, w__i is the edge's weight. It is guaranteed that the graph is connected and doesn't contain loops or multiple edges.

第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 10^5$，），分别表示图的顶点数和边数。接下来是 $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$），其中 $a_i$ 和 $b_i$ 是第 $i$ 条边所连接的两个顶点的编号，$w_i$ 是该边的权重。保证该图是连通的，且不包含自环或重边。

Print m lines — the answers for all edges. If the i-th edge is included in any MST, print "any"; if the i-th edge is included at least in one MST, print "at least one"; if the i-th edge isn't included in any MST, print "none". Print the answers for the edges in the order in which the edges are specified in the input.

输出 m 行——即所有边对应的答案。若第 i 条边被包含在任意一棵最小生成树（MST）中，则输出 "any"；若第 i 条边至少被包含在某一棵 MST 中，则输出 "at least one"；若第 i 条边不被包含在任何 MST 中，则输出 "none"。请按照输入中边的给定顺序输出各边的答案。

In the second sample the MST is unique for the given graph: it contains two first edges.

In the third sample any two edges form the MST for the given graph. That means that each edge is included at least in one MST.

在第二个样例中，给定图的最小生成树（MST）是唯一的：它包含前两条边。

在第三个样例中，任意两条边都构成给定图的最小生成树。这意味着每条边至少被包含在某一个最小生成树中。