Society Members

Time limit1sMemory limit128 MB

Summary

Given nested society membership definitions with possible society-name references, compute the total number of distinct human members in the first listed society.

Level: Medium4 of 10
Topics: Graph, DFS, Hash map
Solved: No attempts yet

Problem

Sanggeun is the president of the Sogang ACM-ICPC Team. Students in computer-related studies at Sogang University belong to one or more societies, and Sanggeun wants to find out which societies each student belongs to.

Sanggeun records the membership information in the following format. The example below means that sisobus and weissblume are members of the society icpc.

icpc:weissblume,sisobus.

Before the colon (:) is the name of the society; after it is the list of that society's members.

A society may have members who all belong to other societies. Therefore, instead of a person's name, the name of another society may be written in the member list.

slug:sisobus,minhyeok,icpc,exupery.

This means that everyone who belongs to icpc also belongs to slug. In other words, if we expand every member of slug, we get:

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

Here sisobus appears twice. If we merge duplicate names into one, it can be written more compactly as:

slug:sisobus,minhyeok,weissblume,exupery.

Given the membership information of the societies, write a program that finds how many members each society has.

In Sanggeun's notation, society names may be nested several levels deep. In the example below, only one member, abckhw, actually belongs to one.

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

Input

The input consists of several test cases. The first line of each test case contains the number of societies $n$ . $n$ is a positive integer not greater than $100$ .

The next $n$ lines each give one society's membership in the format described above. Before the colon (:) is the society name, and after it the member names are listed separated by commas (,). Each line ends with a single period (.).

All society names are distinct. If a name in a member list is not a society name, then it is a person's name.

The given society information contains no cycles.

Each society or person name is a non-empty string of length between $1$ and $15$ , consisting only of lowercase letters. The number of societies or people listed directly in each society is between $1$ and $10$ .

The last line of the input contains a single $0$ .

Output

For each test case, print on one line the number of members belonging to the first society given.

Examples1

Example 1

Input

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

Expected output