학회원

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

요약
단체 이름이 다른 단체를 중첩해서 참조할 수 있는 회원 목록이 주어질 때, 첫 번째 단체에 속한 서로 다른 사람 수를 구합니다.
난이도

보통10점 중 4점

유형
그래프, DFS, 해시맵
정답자
아직 제출이 없습니다

문제

상근이는 Sogang ACM-ICPC Team의 회장이다. 서강대학교의 컴퓨터 관련 학생들은 하나 이상의 학회에 소속되어 있다. 상근이는 각 학생이 어떤 학회에 소속되어 있는지 조사하려고 한다.

상근이는 학회원 정보를 다음과 같은 형식으로 적는다. 아래 예시는 sisobus와 weissblume이 icpc 학회의 회원이라는 뜻이다.

icpc:weissblume,sisobus.

콜론(:) 앞에는 학회의 이름을, 뒤에는 그 학회의 회원 목록을 쓴다.

어떤 학회는 회원이 모두 다른 학회에 소속되어 있을 수도 있다. 따라서 회원을 적는 자리에 사람 이름 대신 다른 학회의 이름을 적을 수도 있다.

slug:sisobus,minhyeok,icpc,exupery.

이는 icpc에 소속된 사람은 모두 slug에도 소속된다는 뜻이다. 즉, slug의 회원을 모두 펼쳐 쓰면 다음과 같다.

slug:sisobus,minhyeok,weissblume,sisobus,exupery.

이때 sisobus가 두 번 나타난다. 중복되는 사람의 이름을 하나로 합치면 다음과 같이 줄여서 쓸 수 있다.

slug:sisobus,minhyeok,weissblume,exupery.

학회의 회원 정보가 주어졌을 때, 각 학회의 학회원이 몇 명인지 구하는 프로그램을 작성하시오.

상근이가 정보를 적는 방식에서는 학회의 이름이 여러 단계로 중첩될 수도 있다. 아래 예시에서 one에 실제로 소속된 회원은 abckhw 한 명뿐이다.

one:another.
another:yetanother.
yetanother:abckhw.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 학회의 수 nn이 주어진다. nn은 100100 이하의 양의 정수이다.

다음 nn개의 줄에는 각 학회의 회원 정보가 문제에서 설명한 형식으로 주어진다. 콜론(:) 앞은 학회 이름이고, 뒤에는 회원 이름이 콤마(,)로 구분되어 나열된다. 각 줄의 끝에는 마침표(.)가 하나 붙는다.

학회 이름은 서로 모두 다르다. 회원 목록에 등장하는 이름이 학회 이름이 아니라면, 그 이름은 사람의 이름이다.

주어지는 학회 정보에는 순환을 이루는 정보가 없다.

각 학회 또는 사람의 이름은 비어 있지 않으며, 길이가 11 이상 1515 이하이고, 알파벳 소문자로만 이루어져 있다. 각 학회에 직접 나열된 학회 또는 사람의 수는 11 이상 1010 이하이다.

입력의 마지막 줄에는 00이 하나 주어진다.

출력

각 테스트 케이스에 대해, 제일 처음으로 주어지는 학회에 포함되어 있는 회원의 수를 한 줄에 출력한다.

예제1

  1. 예제 1

    입력
    2
    development:alice,bob,design,eve.
    design:carol,alice.
    3
    one:another.
    another:yetanother.
    yetanother:dave.
    3
    friends:alice,bob,bestfriends,carol,fran,badcompany.
    bestfriends:eve,alice.
    badcompany:dave,carol.
    5
    a:b,c,d,e.
    b:c,d,e,f.
    c:d,e,f,g.
    d:e,f,g,h.
    e:f,g,h,i.
    4
    aa:bb.
    cc:dd,ee.
    ff:gg.
    bb:cc.
    0
    
    예상 출력
    4
    1
    6
    4
    2