시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 118 21 13 15.294%

문제

새로운 검색 엔진을 만들었다. 이 검색 엔진은 구글을 뛰어넘는 세계 최고의 검색 엔진이기 때문에, 신뢰도가 높은 결과를 보여줘야 한다. 하지만, 사용자가 검색어를 입력했을 때, 이것에 맞는 결과가 수천, 수만개가 될 수 있으므로, 이 중에 어떤 것이 중요하고, 어떤 사이트를 보여줘야 하는지가 큰 문제이다.

구글은 이러한 것을 사이트를 크롤링해서 자체 알고리즘을 이용해서 사이트의 순위를 매긴다.

우리의 검색 엔진은 다음과 같은 방법을 사용할 것이다.

일단 모든 웹사이트에 1점을 준다. 만약에 웹사이트 A에 웹사이트 B로 가는 링크가 있다면, 웹사이트 B의 점수에 웹사이트 A의 점수를 더한다.

예를 들어, 웹사이트가 총 3개가 있다. A, B, C이다. 일단 모든 웹사이트의 점수는 1이다. 이제, 웹사이트 A와 B에 모두 C로 가는 링크가 있다고 하면, C의 점수는 3이 되고, A와 B의 점수는 그대로 1이다. 만약 어떤 검색어가 입력 됬는데, 이 웹사이트 A B C에 모두 해당하는 것이었다면, C가 가장 위에 표시된다.

이런 웹사이트에 점수를 매기는 일이 어려운 이유는 바로, 링크를 교환하는 사이트 들이 있기 때문이다. 이 말은 A가 B를 링크하고, B가 A를 링크하는 것이다. 따라서, 이런 현상으로 점수가 무한대로 늘어나는 것을 방지하기 위해서, A의 점수를 B에 더할 때는, B에서 A로의 링크가 직접적으로 또는 간접적으로 없을 때이다.

링크가 어떻게 되어있는 지가 주어지고, 웹사이트의 이름이 주어질 때, 그 웹사이트의 점수를 출력하는 프로그램을 작성하시오.
 

입력

첫째 줄에 링크 정보의 개수 N이 주어진다. 이 N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 링크의 정보가 주어진다. 링크의 정보는 다음과 같다. 가장 처음 등장하는 문자열은 웹사이트의 이름이다. 그 다음에 등장하는 수는 그 웹사이트를 가리키고 있는 웹사이트 이름의 개수이다. 그 개수 만큼 웹사이트의 이름이 주어진다. 예를 들어, C 2 A B 라면, A->C로 가는 링크가 있고, B->C로 가는 링크가 있는 것이다.마지막 줄에는 웹사이트의 이름이 주어진다. 이 웹사이트의 점수를 출력하는 것이다. 웹사이트의 이름은 알파벳 대문자로만 이루어져 있으며 길이는 최대 50이다. 다른 제한은 모두 50이다. 그리고, 링크의 정보에서 처음 등장하는 문자열 즉 웹사이트의 이름은 같은 것이 여러번 나오지 않는다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력

3
A 3 B C D
B 2 C D
C 1 D
A

예제 출력

8

힌트

출처