Background

Translation source: loj #5460. 「ROI 2012 Day 2」The Theatre Begins with the Actors.

Problem Description

Olympiad participants came to the Kazan theatre to watch a performance. There are $N$ actors in the play whom they do not know. In the theatre lobby, portraits of all actors in the troupe are displayed, and the whole troupe takes part in the performance, but the portraits have no names. The audience received a playbill that lists, for each act, the surnames of the actors participating in that act, but it does not state their roles.

A theatre fan, Vitaly, decided to find out what each actor mentioned in the playbill looks like. To do this, during the intermission after each act, he goes to the lobby and compares the portraits with the actors he has seen.

You need to write a program that, given the number of actors $N$ and the lists of surnames of actors participating in each of the $M$ acts, determines after which act it becomes possible for the first time to determine the correspondence between the surnames in the playbill and the portraits.

Input Format

The first line of the input file contains two natural numbers $N$ and $M$ $(1 < N \leq 100000, 1 \leq M \leq 100000)$, representing the number of actors and the number of acts, respectively.

The next $M$ lines describe the acts. Each line starts with an integer $K_i$ $(1 \leq K_i \leq N, K_1 + K_2 + \ldots + K_M \leq 100000)$, the number of actors participating in the $i$-th act, followed by $K_i$ distinct natural numbers (not exceeding $N$), which are the surname IDs of the actors participating in this act. Adjacent numbers in a line are separated by spaces.

Output Format

Output one line containing $N$ integers separated by spaces. The $i$-th integer indicates after which act it becomes possible for the first time to determine the correspondence between the $i$-th actor and their portrait. If it is still impossible to determine the correspondence for some actor even after the performance ends, output $0$ in that position.

3 3
2 1 2
2 3 2
2 1 2

2 2 1

5 3
3 1 2 3
3 2 3 1
2 1 3

0 3 0 0 0

4 3
1 1
1 3
1 2

1 3 2 3

Hint

In the first sample, three actors participate in a performance consisting of three acts. The first act has two actors, numbered $1$ and $2$. Since there are three actors in total, after the first act ends, it is possible to determine that the portrait of actor $3$ corresponds to surname ID $3$, so the third number in the output line is $1$.

The second act has two actors, numbered $3$ and $2$. Since only actor $2$ participates in both the first and the second act, after the second act ends, it is possible to determine their portrait. Also, since there are three portraits in total, after the second act ends it is possible to determine that the remaining portrait corresponds to actor $1$. The third act does not affect the result.

Detailed additional constraints and scores for subtasks are given in the table below:

Translated by ChatGPT 5