만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

감염 의심자

면접 대비

시간 제한1초메모리 제한128 MB

요약
0번 학생과 같은 모임으로 직간접적으로 연결된 용의자 수를 셉니다.
난이도

쉬움10점 중 3점

유형
유니온 파인드
정답자
아직 제출이 없습니다

문제

중증급성호흡기증후군(SARS)은 원인을 알 수 없는 비정형 폐렴으로, 2003년 3월 중순에 전 세계적인 위협으로 인식되었다. 전파를 최소한으로 줄이려면 감염 의심자를 다른 사람과 분리하는 것이 가장 좋다.

NSYSU(Not-Spreading-Your-Sickness University)에는 학생 모임이 아주 많다. 같은 모임에 속한 학생은 서로 자주 접촉하고, 한 학생이 여러 모임에 가입하기도 한다. SARS 전파를 막으려고 NSYSU는 모든 학생 모임의 명단을 모은 뒤 표준 운영 절차에 다음 규칙을 넣었다.

모임에 감염 의심자가 한 명이라도 있으면, 그 모임의 학생은 모두 감염 의심자다.

그런데 어떤 학생이 감염 의심자로 판정되었을 때 의심자 전체를 손으로 가려내기는 쉽지 않다. 감염 의심자를 모두 찾는 프로그램을 작성하라.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 정수 nn과 mm이 주어진다. nn은 학생 수, mm은 모임 수이고 0<n≤300000 < n \le 30000, 0≤m≤5000 \le m \le 500이다. 학생은 00부터 n−1n-1까지 서로 다른 번호를 하나씩 받으며, 모든 테스트 케이스에서 학생 00은 처음부터 감염 의심자로 판정된 상태다. 이 줄 다음에는 모임 mm개의 명단이 한 줄에 하나씩 주어진다. 각 줄은 그 모임의 인원 수 kk로 시작하고, 이어서 그 모임에 속한 학생 번호가 kk개 나온다. 한 줄에 있는 정수는 하나 이상의 공백으로 구분된다.

n=0n = 0이고 m=0m = 0인 테스트 케이스는 입력의 끝을 뜻하며, 처리하지 않는다.

출력

각 테스트 케이스마다 감염 의심자의 수를 한 줄에 출력한다.

예제1

  1. 예제 1

    입력
    100 4
    2 1 2
    5 10 13 11 12 14
    2 0 1
    2 99 2
    200 2
    1 5
    5 1 2 3 4 5
    1 0
    0 0
    
    예상 출력
    4
    1
    1