There is an ancient tree with vertices and edges. The vertices are numbered through . A magic ritual lasts days. On the -th day, there is a subset
of edges being chosen, and you can choose to keep the edges in and discard the rest, or you can choose to keep the remaining edges in and discard all edges in . Either way, the vertices in 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 , if you are able to decide whether keeping the edges in or for each day, what is the maximum possible size of the intersection of the connected components containing  on all days?
As this is a forbidden ritual, you will not be given the tree nor the set of edges on each day. Instead, you will only receive the information of the connected components after keeping edges in or respectively for each day. It can be shown that the answer can be uniquely determined given the information.

输入描述:

The first line contains two integers , denoting the size of the tree and the duration of the magic ritual in days, respectively.

Then the information of the  days of the magic ritual follows. The information of the th day of the magic ritual is given as follows:

First, the description of the connected components in the graph  is given. The first line consists of an integer , denoting the number of connected components after keeping all edges in  and discarding the rest.

Then  lines follow, in the -th line an integer  is given, denoting the size of a connected component, then  integers  follows, denoting the number of vertices in the connected component. It is guaranteed that the input given by the  lines forms a valid decomposition of the vertices.

Then the description of the connected components in the graph  is given. A line follows with an integer , denoting the number of connected components after keeping edges in  and discarding all edges in .

Then  lines follow, in the -th line an integer  is given, denoting the size of a connected component, then  integers  follows, denoting the number of vertices in the connected component. It is guaranteed that the input given by the  lines forms a valid decomposition of the vertices.

It is guaranteed that there exists at least one tree  and choices of  that are consistent with the input.

输出描述:

The output consists of a line containing  integers, denoting the answer for the vertices , 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  and choices of  corresponding to the input, is given as ,  and , as shown in the following graphs, where red edges represent edges in  and , and blue edges represent edges in  and , respectively.





For vertex , one optimal way is to keep  and , leading to an intersection set  of size .

For vertex , one optimal way is to keep  and , leading to an intersection set  of size .

For vertex , one optimal way is to keep  and , leading to an intersection set  of size .

For vertex , one optimal way is to keep  and , leading to an intersection set  of size .

For vertex , one optimal way is to keep  and , leading to an intersection set  of size .

For vertex , one optimal way is to keep  and , leading to an intersection set  of size .