P17891 [ICPC 2026 Nanchang I] Eating Cherries
Description
Jiangqiao loves eating cherries! Before the cherries ripened, he had already arrived at the cherry tree...
A cherry tree consists of $n$ nodes (numbered $1$ to $n$) and $n - 1$ branches, which connect all the nodes together.
Jiangqiao classifies the cherries on the whole cherry tree into $m$ types (numbered $1$ to $m$) based on size, color, sweetness, etc., where node $i$ has $k_i$ types of cherries.
A **main branch** is the path from the root node to a certain leaf node without repeating any node.
That is, for root node $u$, the main branch from $u$ to a leaf node $v$ is a node sequence $[u = x_0, x_1, x_2, \ldots, x_s = v]$,
where node $x_i$ is connected to node $x_{i+1}$ ($i < s$) by a branch, and $x_i \neq x_j$ whenever $i \neq j$.
A **leaf node** refers to a node that is connected to only one branch with other nodes. Specifically, **the root node is not a leaf node**.
Obviously, for each leaf node, the main branch from the root to it is uniquely determined.
Jiangqiao can cast magic. **Each spell** can choose a leaf node and **arbitrarily change** the cherry types and the number of types on that node (including making it cherry-free).
He wants to know, for each node $1,2,...,n$ serving as the root, the **minimum number of spells** needed so that the **set of cherry types** on every main branch is the same.
Input Format
The first line contains two integers $n$ and $m$ ($2 \le n \le 2 \times 10^5$, $1 \le m \le 6$) --- the number of nodes and the number of cherry types.
Each of the next $n - 1$ lines contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$) --- a branch on the tree.
Each of the next $n$ lines describes a node. The $i$-th of these lines starts with a non-negative integer $k_i$ ($0 \le k_i \le m$) --- the number of cherry types at node $i$. If $k_i > 0$, it is followed by $k_i$ distinct integers $t_{i,1}, t_{i,2}, \ldots, t_{i,k_i}$ ($1 \le t_{i,j} \le m$) --- the cherry types.
It is guaranteed that all nodes are connected by the branches.
Output Format
A single line containing $n$ non-negative integers, where the $i$-th integer is the answer when node $i$ is the root.