Cây xương rồng nhiều màu

Một cây xương rồng cạnh (edge cactus) là một đồ thị vô hướng liên thông, không có khuyên và không có cạnh song song, trong đó mỗi cạnh thuộc về nhiều nhất một chu trình.

Cho một cây xương rồng cạnh với $n$ đỉnh và $m$ cạnh, mỗi cạnh được tô một màu. Bạn cần xoá đi một số cạnh sao cho đồ thị còn lại trở thành một cây (liên thông và không có chu trình). Trong tất cả các cách xoá số cạnh ít nhất để đạt được điều đó, hãy tìm số màu khác nhau nhiều nhất có thể có trên các cạnh của cây thu được.

Vì mỗi cạnh thuộc nhiều nhất một chu trình, để biến đồ thị thành cây ta phải xoá đúng một cạnh khỏi mỗi chu trình (và giữ nguyên mọi cạnh không nằm trong chu trình nào). Bạn được tự do chọn xoá cạnh nào trong mỗi chu trình.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$: số đỉnh và số cạnh.
• $m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u$, $v$, $c$: một cạnh nối hai đỉnh $u$ và $v$ có màu $c$.

Đảm bảo đồ thị cho trước là một cây xương rồng cạnh.

Dữ liệu ra

In ra một số nguyên: số màu khác nhau nhiều nhất mà cây thu được có thể có.

Ràng buộc

• $2\le n\le 10000$
• $1\le u,v\le n$, $u\ne v$
• $1\le c\le m$

Ví dụ