160_D. 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.

Input

The first line contains two integers n and m (2 ≤ n ≤ 105, <image>) — 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 "ai bi wi" (1 ≤ ai, bi ≤ n, 1 ≤ wi ≤ 106, ai ≠ bi), where ai and bi are the numbers of vertexes connected by the i-th edge, wi is the edge's weight. It is guaranteed that the graph is connected and doesn't contain loops or multiple edges.

Output

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.

Examples

Input

4 5
1 2 101
1 3 100
2 3 2
2 4 2
3 4 1


Output

none
any
at least one
at least one
any


Input

3 3
1 2 1
2 3 1
1 3 2


Output

any
any
none


Input

3 3
1 2 1
2 3 1
1 3 1


Output

at least one
at least one
at least one

Note

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.
```python
import sys
from math import inf
from collections import defaultdict

    
class disjoinSet(object):
    def __init__(self,n):
        self.father = [x for x in range(0,n+1)]
        self.rank = [0 for x in range(0,n+1)]

    def setOf(self, x):
        if(self.father[x] != x):
            self.father[x] = self.setOf(self.father[x])
        return self.father[x]

    def Merge(self,x,y):
        xR = self.setOf(x)
        yR = self.setOf(y)
        if(xR == yR):
            return
        if self.rank[xR] < self.rank[yR]:
            self.father[xR] = yR
        elif self.rank[xR] > self.rank[yR]:
            self.father[yR] = xR
        else:
            self.father[yR] = xR
            self.rank[xR] +=1

def merge(left,right):
    result = []
    l,r=0,0
    while l < len(left) and r < len(right):        
        if left[l][2] <= right[r][2]:            
            result.append(left[l])
            l+=1            
        else:
            result.append(right[r])
            r+=1
    result += left[l:]
    result += right[r:]    
    return result

def mergesort(x):    
    if len(x) < 2:
        return x   
    middle = int(len(x)/2)    
    left = mergesort(x[:middle])
    right = mergesort(x[middle:])
    return merge(left,right)
    

def DFS(graph,bridges):
    time = 0
    for key in graph:
        low[key] = inf
        d[key] = -1
        pi[key] = key
        visited[key] = False
    for i in graph:
        if not visited[i]:
            DFS_Visit(graph,i,bridges)
    
def DFS_Visit(graph,u,bridges):
    visited[u] = True
    global time
    time +=1
    d[u] = time    
    low[u] = d[u]
    for v in graph[u]:
        if not visited[v]:
            pi[v] = u
            DFS_Visit(graph,v,bridges)
            low[u] = min(low[u],low[v])
        elif pi[u] != v:
            low[u] = min(low[u],d[v])
    if pi[u] != u and low[u] >= d[u]:
        x = min(pi[u],u)
        y = max(pi[u],u)            
        bridges.append([x,y])
    time +=1


time = 0
n, m = map(int, sys.stdin.readline().split())

if m <= n-1:
    for _ in range(0,m):
        print("any")
    exit()


visited = {}
d = {}
low = {}
pi = {}

edges = []

for i in range(0,m):
    x,y,z = map(int, sys.stdin.readline().split())    
    
    edges.append([])
    edges[i] = [x,y,z]    

dsu = disjoinSet(n)    

ans = {}
for i in edges:
    x = min(i[0],i[1])
    y = max(i[0],i[1])
    ans[x,y] = "at least one"    

sortEdges = mergesort(edges)

criticalEdges = []
i = 0
cantEdges = m
while i < cantEdges:        
    j = i;
    a = 0
    b = 0
    criticalEdges = []
    while j < len(sortEdges) and sortEdges[j][2] == sortEdges[i][2]:
        x = dsu.setOf(sortEdges[j][0])
        y = dsu.setOf(sortEdges[j][1])
        a = min(sortEdges[j][0],sortEdges[j][1])
        b = max(sortEdges[j][0],sortEdges[j][1])
        if x == y:            
            ans[a,b] = "none"
        criticalEdges.append(sortEdges[j])
        j+=1
    if len(criticalEdges) == 1:
        if ans[a,b] != "none":
            ans[a,b] = "any"
            dsu.Merge(a,b)                
    else:
        graph = defaultdict(set)
        crossCut = defaultdict(list)
        for m in criticalEdges:
            x = min(dsu.setOf(m[0]),dsu.setOf(m[1]))
            y = max(dsu.setOf(m[0]),dsu.setOf(m[1]))
            if x != y:
                graph[x].add(y)
                graph[y].add(x)
                crossCut[x,y].append([min(m[0],m[1]),max(m[0],m[1])])
        bridges = []
        DFS(graph,bridges)
        for k in bridges:
            if len(crossCut[k[0],k[1]]) == 1:
                ans[crossCut[k[0],k[1]][0][0],crossCut[k[0],k[1]][0][1]] = "any"

            
        for m in criticalEdges:
            if dsu.setOf(m[0]) != dsu.setOf(m[1]):
                dsu.Merge(m[0],m[1])            
    i = j
    
for i in edges:
    x = min(i[0],i[1])
    y = max(i[0],i[1])
    print(ans[x,y])          



```