Tô màu kem

Cho một cây $T$ gồm $n$ đỉnh và $m$ loại kem được đánh số từ $1$ đến $m$. Đỉnh thứ $i$ của cây chứa một tập gồm $s_i$ loại kem đôi một khác nhau.

Dữ liệu đảm bảo: với mỗi loại kem $i$, tập các đỉnh của $T$ có chứa loại kem $i$ tạo thành một đồ thị con liên thông của $T$ (tập rỗng cũng được coi là liên thông).

Từ cây $T$, ta dựng đồ thị $G$ gồm $m$ đỉnh, mỗi đỉnh ứng với một loại kem. Trong $G$ có cạnh nối đỉnh $u$ và đỉnh $v$ ($u\ne v$) khi và chỉ khi tồn tại ít nhất một đỉnh của $T$ chứa đồng thời cả loại kem $u$ và loại kem $v$.

Hãy tô màu tất cả các đỉnh của $G$ sao cho hai đỉnh kề nhau luôn được tô hai màu khác nhau, và số màu được dùng là ít nhất có thể.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$ — số đỉnh của cây và số loại kem.
• $n$ dòng tiếp theo, dòng thứ $i$ bắt đầu bằng số nguyên $s_i$, sau đó là $s_i$ số nguyên đôi một khác nhau trong đoạn $[1,m]$ — các loại kem có ở đỉnh $i$.
• $n-1$ dòng cuối, mỗi dòng chứa hai số nguyên $u$ và $v$ — một cạnh của cây $T$.

Dữ liệu ra

• Dòng đầu in ra số nguyên $c$ — số màu ít nhất cần dùng.
• Dòng thứ hai in ra $m$ số nguyên, số thứ $i$ là màu của đỉnh $i$ trong $G$, mỗi màu nằm trong đoạn $[1,c]$.

Nếu có nhiều cách tô thoả mãn, in ra một cách bất kỳ.

Ràng buộc

• $1\le n,m\le 3·{10}^5$
• $0\le s_i\le 3·{10}^5$ và tổng tất cả $s_i$ không vượt quá $5·{10}^5$
• $1\le u,v\le n$

Ví dụ