시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB0000.000%

문제

Участники олимпиады пришли в казанский театр на спектакль, где играют N неизвестных для них актеров. В фойе театра висят портреты всех актеров труппы, которая в полном составе задействована в спектакле. Портреты не подписаны. Зрителям раздали программки, в которых для каждого действия спектакля приводится список фамилий участвующих в нем актеров, но не указаны их роли.

Театрал Виталий решил узнать, как выглядит каждый из актеров, упомянутых в программке. Для этого в антракте после каждого действия он выходил в фойе и сопоставлял портреты с увиденными актерами.

Требуется написать программу, которая по заданному числу актеров N и списку фамилий актеров, участвующих в каждом из M действий, определяет номер действия, после которого впервые становится возможным установить соответствие между фамилией актера из программки и его портретом.

입력

Первая строка входного файла содержит два натуральных числа N – число актеров и M – количество действий в спектакле (1 < N ≤ 100 000, 1 ≤ M ≤ 100 000). В каждой из следующих M строк сначала записано количество актеров Ki, участвующих в i–ом действии (1 ≤ Ki ≤ N, K1 + K2 + … + KM ≤ 100 000), а затем Ki различных натуральных чисел, не превосходящих N, обозначающих фамилии этих актеров. Соседние числа в каждой строке разделены пробелом.

출력

Выходной файл должен содержать одну строку, состоящую из N записанных через пробел чисел. i е число этой строки – это номер действия, после которого впервые становится возможным установить соответствие между i–м актером и его портретом. Если к концу спектакля установить соответствие между каким-либо актером и его портретом так и не удалось, то соответствующее число в строке должно быть равно нулю.

예제 입력 1

3 3
2 1 2
2 3 2
2 1 2

예제 출력 1

2 2 1

예제 입력 2

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

예제 출력 2

0 3 0 0 0

예제 입력 3

4 3
1 1
1 3
1 2

예제 출력 3

1 3 2 3

힌트

В первом примере три актера участвуют в спектакле с тремя действиями. В первом действии участвуют два актера с номерами 1 и 2. Так как актеров всего трое, то после первого акта становится понятно, какой портрет соответствует актеру с номером 3, поэтому третье число строки выходного файла равно 1.

Во втором действии участвуют два актера с номерами 3 и 2. Поскольку только второй актер участвовал и в первом, и во втором действиях, то его портрет можно определить после второго действия. А так как портретов всего три, то после второго действия можно установить, что последний портрет соответствует актеру номер 1. Третье действие на ответ не влияет.