Description
给你一个带权连通的无向图,对于最小生成树,大家都很熟悉了,我这边就不定义了。 对于任意一个连通图显然存在最小生成树, 但是在通常情况下, 一个图的最小生成树是不唯 一的。 你的任务就是:对于给你的图,来确定该图的每条边是否在任意一棵最小生成树中,或者是至少在某一棵最小生成树中,或者是不在最小生成树中。
Input
输入的第一行含有两个整数n和m( 2<=n<=10^5, n-1<=m<=min(10^5,n*(n-1)/2),分别 表示顶点数和边数。
接下来 m行,描述这边的信息,格式为"ai bi wi"(1≤ai,bi≤n,1≤wi≤10^6,ai≠bi),ai,bi为第i条边的两个顶点, wi为这条边的权值。这图保证是连通的且不含有多重边。
Output
输出m行信息, 如果第i条边包含在任何一棵最小生成树中, 那么输出”any”, 如果第i条边至少包含在某一棵最小生成树中,那么输出”at least one ”,如果第 i条边不在任何一棵最小生成树中,那么输出"none"。按输入边的顺序给出答案。
Sample Input
【样例输入1】
4 5
1 2 101
1 3 100
2 3 2
2 4 2
3 4 1
【样例输入2】
3 3
1 2 1
2 3 1
1 3 2
【样例输入3】
3 3
1 2 1
2 3 1
1 3 1
Sample Output
【样例输出1】
none
any
at least one
at least one
any
【样例输出2】
any
any
none
【样例输出3】
at least one
at least one
at least one