시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB184036828319.902%

문제

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

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

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

일단 모든 웹사이트에 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보다 작거나 같은 알파벳 대문자로 이루어진 문자열이다. 한 웹사이트를 가리키고 있는 웹사이트 이름의 수는 24보다 작거나 같은 음이 아닌 정수이다. 한 웹사이트를 가르키고 있는 웹사이트에 대한 정보는 여러 번 등장하지 않는다. 점수를 조사해야 할 웹사이트의 이름은 반드시 링크의 정보에 등장한다.

출력

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

예제 입력 1

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

예제 출력 1

8

예제 입력 2

1
C 2 A B
C

예제 출력 2

3

예제 입력 3

1
A 0
A

예제 출력 3

1

예제 입력 4

2
A 1 B
B 1 A
A

예제 출력 4

1

예제 입력 5

4
A 5 B C D E F
B 1 A
C 1 B
D 1 B
A

예제 출력 5

3

예제 입력 6

1
MYSITE 3 OTHERSITE ANOTHERSITE THIRDSITE
MYSITE

예제 출력 6

4

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: kipa00