Дан связный взвешенный неориентированный граф без петель и кратных ребер.
Напоминаем, что остовным деревом графа называется ациклический связный подграф данного графа, в который входят все его вершины. Весом дерева называется сумма весов входящих в него ребер. Минимальным остовным деревом (MST) графа называется остовное дерево этого графа, имеющее минимальный возможный вес. Очевидно, что для любого связного графа минимальное остовное дерево существует, но, в общем случае, минимальное остовное дерево графа не единственно.
Ваша задача — для каждого ребра данного графа определить: либо оно входит в любое MST, либо оно входит хотя бы в одно MST, либо оно не входит ни в одно MST.
Выходные данные
Выведите m строк — ответы для всех ребер. Если i-е ребро входит в любое MST, выведите «any»; если i-е ребро входит хотя бы в одно MST, выведите «at least one»; если i-е ребро не входит ни в одно MST, выведите «none». Ответы для ребер выводите в том порядке, в котором ребра заданы во входных данных.
Примечание
Во втором примере для данного графа MST единственно: оно содержит первые два ребра.
В третьем примере для данного графа любые два ребра образуют MST. Значит, любое ребро входит хотя бы в одно MST.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 5
1 2 101
1 3 100
2 3 2
2 4 2
3 4 1
|
none
any
at least one
at least one
any
|
|
2
|
3 3
1 2 1
2 3 1
1 3 2
|
any
any
none
|
|
3
|
3 3
1 2 1
2 3 1
1 3 1
|
at least one
at least one
at least one
|