Cantina of Babel

Time limit2sMemory limit256 MB

Summary

Given each character's spoken and understood languages, remove as few characters as possible so every remaining pair can exchange messages through translators.

Level: Medium5 of 10
Topics: Graph, DFS
Solved: No attempts yet

Problem

Every Star Wars character speaks one language, and most of them also understand several languages they cannot speak. Han Solo might speak in Galactic Basic while Chewbacca answers in Shyriiwook. Each one understands the language the other speaks, so the conversation works.

Say that two characters converse if they can exchange messages in both directions. Even when neither understands the other's language, they still converse as long as a chain of characters can translate for them through intermediate languages. Suppose Jabba speaks in Huttese and Boba Fett translates it into Basic, which R2D2 understands. When R2D2 replies in Binary, Luke translates it into Basic and Bib Fortuna translates that back into Huttese for Jabba. Only characters who stay in the cantina can translate.

The cantina holds many characters speaking different languages. Some pairs cannot converse, even when other patrons are willing to translate, and that leads to fights. You are going to ask some patrons to leave. The cantina is a business, so you want to ask as few as possible. Find the size of the smallest set $S$ such that once every character in $S$ leaves, every pair of remaining characters converses.

In the first example, Chewbacca and Grakchawwaa converse with each other, but they are the only two who understand Shyriiwook, so neither converses with anyone else. Once they leave, the remaining five all converse. In the second example, Fran converses with Ian and Polly converses with Spencer, while no other pair converses, so either everyone but Polly and Spencer leaves, or everyone but Fran and Ian.

Input

The first line contains the number of characters in the cantina, $N$ ( $1 \le N \le 100$ ).

Each of the next $N$ lines describes one character. The line starts with the character's name, then the language that character speaks, then 0 to 20 more languages that character understands but does not speak. Every character understands the language they speak. All names are distinct. Names and languages are strings of 1 to 15 letters (a-z and A-Z), digits, and hyphens, and the items on a line are separated by single spaces.

Output

Print one line with the size of the smallest set $S$ of characters to ask to leave so that every pair of remaining characters converses.

Examples3

Example 1

Input

7
Jabba-the-Hutt Huttese
Bib-Fortuna Huttese Basic
Boba-Fett Basic Huttese
Chewbacca Shyriiwook Basic
Luke Basic Jawaese Binary
Grakchawwaa Shyriiwook Basic Jawaese
R2D2 Binary Basic

Expected output

Example 2

Input

6
Fran French Italian
Enid English German
George German Italian
Ian Italian French Spanish
Spencer Spanish Portugese
Polly Portugese Spanish

Expected output

Example 3
Input
```
3
Amee Basic
Bex Basic
Cy Basic
```
Expected output
```
0
```