Đường dây quan trọng

Một mạng điện có $n$ trạm đánh số từ $1$ đến $n$ và $m$ phương án kéo đường dây; đường dây thứ $i$ nối trạm $u_i$ với trạm $v_i$ với chi phí $w_i$. Biết rằng nếu kéo tất cả các đường dây thì mọi trạm đều liên thông với nhau.

Công ty điện lực sẽ chọn ra một tập đường dây sao cho mọi trạm liên thông với nhau và tổng chi phí là nhỏ nhất (gọi là một phương án tối ưu). Có thể có nhiều phương án tối ưu khác nhau. Với mỗi đường dây, hãy cho biết:

• ALL nếu đường dây đó có mặt trong mọi phương án tối ưu;
• SOME nếu nó có mặt trong ít nhất một phương án tối ưu nhưng không phải tất cả;
• NONE nếu nó không có mặt trong phương án tối ưu nào.

Có thể có nhiều đường dây nối cùng một cặp trạm.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n$, $m$.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $u_i,v_i,w_i$ ($u_i\ne v_i$).

Dữ liệu ra

In ra $m$ dòng, dòng thứ $i$ là ALL, SOME hoặc NONE tương ứng với đường dây thứ $i$.

Ràng buộc

• $2\le n\le 5·{10}^4$
• $n-1\le m\le {10}^5$
• $1\le u_i,v_i\le n$, $u_i\ne v_i$
• $1\le w_i\le {10}^9$
• Đồ thị gồm tất cả các đường dây là liên thông.

Ví dụ