Tô màu loại kem

Cho một cây $T$ gồm $n$ đỉnh và $m$ loại kem được đánh số từ $1$ đến $m$. Mỗi đỉnh $i$ của cây chứa một tập gồm $s_i$ loại kem khác nhau. Với mỗi loại kem $t$ (từ $1$ đến $m$), tập các đỉnh trong $T$ chứa loại kem $t$ tạo thành một đồ thị con liên thông của $T$ (quy ước: tập rỗng cũng được coi là liên thông).

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

Hãy tô màu các đỉnh của $G$ sao cho không có hai đỉnh kề nhau cùng màu, với số màu sử dụng là ít nhất.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• $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 phân biệt — danh sách các loại kem ở đỉnh $i$.
• $n-1$ dòng cuối, mỗi dòng chứa hai số nguyên $u$ và $v$ mô tả một cạnh của cây.

Dữ liệu ra

• Dòng đầu in một số nguyên $c$ — số màu nhỏ nhất cần dùng.
• Dòng thứ hai in $m$ số nguyên, số thứ $i$ là màu của đỉnh $i$ trong $G$ (mỗi màu từ $1$ đến $c$).

Nếu có nhiều cách tô hợp lệ, 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$
• $\sum s_i\le 5·{10}^5$
• $1\le u,v\le n$, các cạnh tạo thành một cây.

Ví dụ