또 하나의 EEEE 어려움

이미지 출처: wikipedia.com

Arnar는 직장에서 접하는 온갖 약어와 축약어 때문에 미쳐 가고 있다. DDI, i13n, o11y부터 LASIK까지 없는 것이 없다. 온갖 두문자어의 뜻을 찾아보려고 멈추지 않고서는 반 페이지조차 읽을 수 없다. 결국 그는 이 문제에 대처하기로 하고, 문제가 얼마나 심각해졌는지 보여 주기 위해 자신이 읽는 자료의 복잡도에 관한 정보를 수집하려 한다. 물론 그는 자신의 일을 하느라 바쁘므로, 데이터 세트에 있는 모든 두문자어의 복잡도를 계산하는 일을 여러분에게 맡긴다. 두문자어의 복잡도는 처음 두문자어의 의미를 이해하기 위해 정의해야 하는 두문자어의 개수이다. 예를 들어, LASER의 복잡도는(Stimulated Emission of Radiation에 의한 Light Amplified) $1$이다. 다른 두문자어를 더 이상 참조하지 않기 때문이다. 그러나 DDI의 복잡도는 $5$이다. DNS, DHCP, IPAM을 참조하고, 이들 중 하나가 다시 IP을 참조하기 때문이다. 두문자어는 자기 자신을 참조할 수도 있고 서로를 순환적으로 참조할 수도 있음에 유의한다.

채점

그룹 | 점수 | 제한 조건

1 | 10 | 두문자어는 다른 두문자어를 참조하지 않는다, $1 \leq n \leq 1 \, 000$.

2 | 15 | 모든 두문자어는 참조되기 전에 정의되며, 서로 다른 두 두문자어가 같은 두문자어를 참조하는 경우는 없다, $1 \leq n \leq 1 \, 000$.

3 | 10 | 모든 두문자어는 참조되기 전에 정의되며, 서로 다른 두 두문자어가 같은 두문자어를 참조하는 경우는 없다.

4 | 40 | $1 \leq n \leq 1 \, 000$.

5 | 25 | 추가 제한 조건이 없다.

입력의 첫 줄에는 입력에서 정의되는 두문자어의 개수인 정수 $1 \leq n \leq 30 \, 000$이 주어진다. 다음 $n$개의 줄에는 각각 두문자어 하나의 정의가 주어진다. 각 줄은 정의할 두문자어로 시작하며, 그다음에는 이 두문자어가 참조하는 단어의 개수인 수 $0 \leq k \leq n$이 주어진다. 이어서 $k$개의 단어가 주어진다. 각 단어는 대문자로만 이루어져 있거나 소문자로만 이루어져 있다. 대문자로만 이루어진 단어는 다른 두문자어이고, 나머지는 두문자어가 아니다. 입력의 모든 문자열은 길이가 최대 $20$이며 영문자로만 이루어져 있다. 입력에 있는 모든 문자열의 길이의 합은 최대 $2 \, 000 \, 000$이다. 입력에서 참조되는 모든 두문자어는 입력 어딘가에서 정의된다.

입력에 등장하는 각 두문자어의 복잡도를 두문자어가 입력에서 정의된 순서대로 한 줄에 하나씩 출력한다.

첫 번째 예제에서 LASER, IP, DNS, DHCP는 다른 어떤 두문자어도 참조하지 않으므로 자기 자신만 정의하면 된다. 따라서 이들의 복잡도는 모두 $1$이다. 하지만 LASIK는 LASER을 참조하므로 둘 다 정의해야 하며, 따라서 복잡도는 $2$이다. IPAM가 IP을 참조하는 경우도 마찬가지이므로 복잡도는 $2$이다. DDI을 이해하려면 DNS, DHCP, IPAM를 정의해야 한다. 하지만 IPAM를 이해하려면 IP도 정의해야 하므로 복잡도는 $4$이 아니라 $5$이다.

두 번째 예제에서 YARA, DB, UNIX의 복잡도는 모두 $1$이다. 하지만 이번에는 일부 두문자어가 자기 자신을 참조한다. 그렇더라도 이는 복잡도에 영향을 주지 않는다. PHP를 정의하려면 PHP만 정의하면 된다. 일단 이것이 정의되면 자기 참조가 해결되므로 복잡도는 $1$이다. 마찬가지로 XAMPP의 경우에는 DB와 PHP만 추가로 정의하면 되므로 복잡도는 $3$이다. 같은 이유로 GNU의 복잡도는 $3$이다. 다음으로 HIRD와 HURD는 서로를 순환적으로 참조하므로, 하나를 이해하려면 다른 하나도 이해해야 한다. 둘을 합치면 UNIX도 참조하므로, 둘 중 하나를 이해하려면 HIRD, HURD, UNIX를 정의해야 한다. 따라서 둘의 복잡도는 모두 $3$이다. 마지막으로 GNULINUX는 UNIX을 두 번 참조하지만, 이는 전체적으로 필요한 정의의 개수에 영향을 주지 않는다. GNULINUX를 정의하려면 GNULINUX, UNIX, GNU를 정의해야 하며, 따라서 복잡도는 $3$이다.