Search Engine

Time limit2sMemory limit128 MB

Summary

Given directed links between websites, compute one website's trust score by summing scores of linking sites only when no cycle would result.

Level: Medium6 of 10
Topics: Graph, DFS, Dynamic programming, Topological sort
Solved: No attempts yet

Problem

A search engine wants to rank websites so that, among matching results, websites with higher trust scores appear first.

Initially every website has score 1. If website A has a link to website B, then A's score is added to B's score only when B cannot reach A by following links directly or indirectly. If B can reach A, that link is ignored for scoring, because otherwise cycles could increase scores without bound.

Given the link information and the name of one website, compute that website's score.

Input

The first line contains the number of link-information lines N. N is a positive integer not greater than 50.

Each of the next N lines has the form X K Y1 Y2 ... YK. X is a website name, and K is the number of websites that point to X. Each Yi has a link to X.

The last line contains the name of the website whose score must be computed.

Every website name consists only of uppercase English letters and has length at most 50. Each K is a nonnegative integer not greater than 24. The incoming-link information for the same website does not appear more than once. The website to query always appears in the link information.

Output

Print the answer on the first line.

Examples6

Example 1
Input
```
3
A 3 B C D
B 2 C D
C 1 D
A
```
Expected output
```
8
```
Example 2
Input
```
1
C 2 A B
C
```
Expected output
```
3
```
Example 3
Input
```
1
A 0
A
```
Expected output
```
1
```
Example 4
Input
```
2
A 1 B
B 1 A
A
```
Expected output
```
1
```
Example 5
Input
```
4
A 5 B C D E F
B 1 A
C 1 B
D 1 B
A
```
Expected output
```
3
```

Example 6

Input

1
MYSITE 3 OTHERSITE ANOTHERSITE THIRDSITE
MYSITE

Expected output