8602: Magic Ritual

There is an ancient tree T=(V,E) with $n$ vertices and n−1 edges. The vertices are numbered through 1,2,…,n. A magic ritual lasts $m$ days. On the i(1≤i≤m)-th day, there is a subset
S_i⊆E of edges being chosen, and you can choose to keep the edges in S_i and discard the rest, or you can choose to keep the remaining edges in E∖S_i and discard all edges in S_i. Either way, the vertices in V will be partitioned into several connected components. By the end of the day, the discarded edges will grow back, and the same tree persists the next day.

You wish to compute, for each vertex v∈V, if you are able to decide whether keeping the edges in S_i or E∖S_i for each day, what is the maximum possible size of the intersection of the connected components containing v on all m days?
As this is a forbidden ritual, you will not be given the tree T nor the set of edges S_i on each day. Instead, you will only receive the information of the connected components after keeping edges in S_i or E∖S_i respectively for each day. It can be shown that the answer can be uniquely determined given the information.

The first line contains two integers n,m(1≤n,m≤10⁶,1≤n×m≤10⁶), denoting the size of the tree and the duration of the magic ritual in days, respectively.
Then the information of the $m$ days of the magic ritual follows. The information of the i(1≤i≤m)th day of the magic ritual is given as follows:
First, the description of the connected components in the graph G_i=(V,S_i) is given. The first line consists of an integer a_i(1≤a_i≤n), denoting the number of connected components after keeping all edges in S_i and discarding the rest.
Then a_i lines follow, in the j(1≤j≤a_i)-th line an integer k is given, denoting the size of a connected component, then k integers c_j,1,c_j,2,…,c_j,k follows, denoting the number of vertices in the connected component. It is guaranteed that the input given by the a_i lines forms a valid decomposition of the vertices.
Then the description of the connected components in the graph H_i=(V,E∖S_i) is given. A line follows with an integer b_i(1≤b_i≤n), denoting the number of connected components after keeping edges in E∖S_i and discarding all edges in S_i.
Then b_i lines follow, in the j(1≤j≤b_i)-th line an integer k is given, denoting the size of a connected component, then k integers d_j,1,d_j,2,…,d_j,k follows, denoting the number of vertices in the connected component. It is guaranteed that the input given by the b_i lines forms a valid decomposition of the vertices.
It is guaranteed that there exists at least one tree T and choices of S₁,S₂,…,S_m that are consistent with the input.

The output consists of a line containing n integers, denoting the answer for the vertices 1,2,…,n, respectively.

6 2
3
4 1 2 3 4
1 5
1 6
4
3 2 5 6
1 1
1 3
1 4
3
4 2 3 5 6
1 1
1 4
4
2 1 2
2 3 4
1 5
1 6

2 3 2 2 3 3

For the sample test, one valid tree T=(V,E) and choices of S₁,S₂ corresponding to the input, is given as E={(1,2),(2,3),(3,4),(2,5),(2,6)}, S₁={(1,2),(2,3),(3,4)} and S₂={(2,3),(2,5),(2,6)}, as shown in the following graphs, where red edges represent edges in S₁ and S₂, and blue edges represent edges in E∖S₁ and E∖S₂, respectively.


For vertex $1$, one optimal way is to keep S₁ and E∖S₂, leading to an intersection set {1,2} of size $2$.
For vertex $2$, one optimal way is to keep E∖S₁ and S₂, leading to an intersection set {2,5,6} of size $3$.
For vertex $3$, one optimal way is to keep S₁ and S₂, leading to an intersection set {2,3} of size $2$.
For vertex $4$, one optimal way is to keep S₁ and E∖S₂, leading to an intersection set {2,3} of size $2$.
For vertex $5$, one optimal way is to keep E∖S₁ and S₂, leading to an intersection set {2,5,6} of size $3$.
For vertex $6$, one optimal way is to keep E∖S₁ and S₂, leading to an intersection set {2,5,6} of size $3$.