D. Eating Cherries
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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 \lt 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

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 \gt 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

A single line containing $$$n$$$ non-negative integers, where the $$$i$$$-th integer is the answer when node $$$i$$$ is the root.

Example
Input
5 2
1 2
2 3
2 4
4 5
1 1
1 1
2 1 2
0
1 1
Output
1 1 0 1 1