Cho \(G\) là đồ thị vô hướng liên thông không chứa khuyên (khuyên là cạnh nối một đỉnh với chính nó) với \(N\) đỉnh và \(M\) cạnh. Các đỉnh của đồ thị được đánh số từ l đến \(N\). Hãy tìm cách gán cho mỗi cạnh của \(G\) một nhãn là một số từ 1 đến \(M\) sao cho không có hai cạnh nào có cùng nhãn, và mồi đỉnh với bậc lớn hơn 1, ước chung lớn nhất của các nhãn trên các cạnh kề nó là 1.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(M\) được ghi cách nhau bởi dấu cách (\(N < 10^5; M < 250000\));
• Mỗi dòng trong số \(M\) dòng tiếp theo chứa hai số \(x\) và \(y\) được ghi cách nhau bởi dấu cách, cho biết có cạnh nối giữa các nút \(x\) và \(y\).

Output

• Ghi ra \(M\) dòng, mỗi dòng chứa ba số nguyên dương \(x,y,v\) được ghi cách nhau bởi dấu cách cho biết cạnh (\(x, y\)) được gán nhãn \(v\).

Example

5 6
1 2
2 3
1 3
4 1
3 4
3 5 

1 2 2
1 4 1
1 3 3
3 2 5
3 4 4 
3 5 6