Laiko ribojimas: 1s

Atminties ribojimas: 1024MB

Duomenų failas: mst_keliai.in

Rezultatų failas: mst_keliai.out

Jei norite pateikti savo sprendimą - prisijunkite.

4. Domantas ir MST keliai

Jums duotas jungus svorinis grafas su neorientuotomis briaunomis.

Jūsų užduotis - kiekvienai grafo briaunai nustatyti ar ji įeina į visus grafo minimalaus svorio jungiamuosius medžius (minimum spanning tree), ar tik į dalį, ar į nė vieną minimalaus svorio jungiamąjį medį.

Pradiniai duomenys

Pirmoje eilutėje pateikti du sveikieji skaičiai n, m (2\\leqn\\leq10^5,n-1\\leqm\\leq10^5) - grafo viršūnių bei briaunų kiekis.

Sekančiose m eilučių pateikta po tris sveikuosius skaičius a_i,b_i,w_i (1\\leqa_i,b_i\\leqn,0\\leqw_i\\leq10^6,a_i\\neqb_i) - grafo briaunų aprašymas. Grafo viršūnės a_i,b_i yra sujungtos briaunos su svoriu w_i.

Rezultatai

Išspausdinkite m eilučių - kiekvienai briaunai po atsakymą. Jei i-toji briauna patenka į visus minimalaus svorio jungiamuosius medžius, išspausdinkite "any", jei patenka bent į vieną, išspausdinkite "at least one", kitu atveju išspausdinkite "none".

Pavyzdžiai

Pradiniai duomenys Rezultatai 
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