J. TeamsCode Meetings
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Bossologist is tired of attending both weekly TeamsCode meetings, so now he's making the other problem setters go for him! Problem ideas are discussed in meetings which occur every $$$N$$$ days in an "$$$N$$$-day week," with days of the week being numbered $$$1,2,\dots,N-1, N, 1, 2,\dots$$$ There are $$$M$$$ problem setters (not including Bossologist) the $$$i$$$-th of which go to $$$p_i$$$ different meetings a week.

When a problem idea is made, Bossologist is in charge of going to the meetings and making sure the other problem setters are "aware," or informed of the idea. At first none of the setters are "aware," but they become "aware" by attending the same meeting as either Bossologist or another aware problem setter. A meeting is called "productive" if Bossologist or at least one aware setter attends that meeting. Bossologist would like to figure out the minimum amount of meetings he must attend given that all meetings within $$$N$$$ days of an idea's conception must be productive.

Input

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N$$$, $$$M \leq 10^5$$$) denoting the number of days in the week and the number of problem setters respectively.

The next $$$M$$$ lines contain several space separated integers. The first one $$$p_i$$$ ($$$1 \leq p_i \leq N$$$) decribes the number of meetings problem setter $$$i$$$ is attending. The next $$$p_i$$$ integers denote the days of the week that problem setter $$$i$$$ attends meetings (in sorted order). The sum of all $$$p_i$$$ is guaranteed to be less than or equal to $$$5 \cdot 10^5$$$.

Testcases in subtasks are numbered from $$$1$$$ to $$$20$$$ with samples skipped.

Testcases $$$1−5$$$: $$$N$$$, $$$M \leq 1000$$$.

Testcases $$$6−20$$$: No additional constraints.

Output

$$$N$$$ lines, where the $$$i$$$-th line is a single integer representing the minimum number of meetings Bossologist must attend if a problem idea is conceived on the $$$i$$$-th day of the week.

* Note that days in which no problem setter attends a meeting are not counted toward the answer

Example
Input
4 3
2 1 3
2 3 4
2 2 4
Output
2
2
1
2
Note

If a problem idea is created on day $$$1$$$ or $$$2$$$, Bossologist has to attend the meetings on days $$$1$$$ and $$$2$$$.

If a problem idea is created on day $$$3$$$, Bossologist has to attend the meeting on days $$$3$$$.

If a problem idea is created on day $$$4$$$, Bossologist has to attend the meeting on days $$$1$$$ and $$$4$$$.

 —

Problem Idea: Bossologist

Problem Preparation: Bossologist

Occurrences: Novice 11, Advanced 5