임포트 스파게티

프로그래밍 학교를 갓 졸업하고 파이썬 개발자로 취직했다. 출근 첫날, 엉망인 코드를 물려받았다는 사실을 알게 됐다. 이전 담당자는 스파게티 설계를 고른 뒤 얼마 전 해외로 떠났다. 코드를 읽어 보려 하자마자 여러 파일이 서로 순환하며 의존하고 있다는 것을 발견했다. 테스트는커녕 실행조차 시도된 적이 없다.

자리에 앉아 고민한 끝에, 가장 먼저 할 일은 의존 그래프에서 순환을 없애는 것이라고 결론지었다. 그래서 가장 짧은 의존 순환을 찾는 일부터 시작한다.

첫째 줄에 파일의 개수 $n$이 주어진다 ($1 \le n \le 500$). 둘째 줄에 서로 다른 파일 이름 $n$개가 주어진다. 각 이름은 소문자 'a'부터 'z'까지로만 이루어진 길이 1 이상 8 이하의 문자열이다.

이어서 $n$개의 구역이 둘째 줄에 나온 순서대로 주어진다. 각 구역의 첫 줄에는 파일 이름과 정수 $k$가 있고, 그 뒤로 import로 시작하는 줄이 $k$개 이어진다. import 줄은 import 다음에 의존하는 파일 이름을 , 로 구분해 나열한다.

한 파일이 같은 파일을 두 번 import 하지는 않으며, import 되는 파일은 모두 둘째 줄에 나온다. 파일은 자기 자신을 import 할 수 있고, 이때 길이가 1인 순환이 된다.

순환 의존이 없으면 SHIP IT을 출력한다. 순환이 있으면 가장 짧은 순환에 속한 파일 이름을 순환을 따라가는 순서대로 공백 하나로 구분해 한 줄에 출력한다.

가장 짧은 순환이 여러 개일 수도 있고, 같은 순환을 어느 파일에서 시작해 적느냐에 따라 여러 가지로 쓸 수도 있다. 그중 사전순으로 가장 앞서는 나열 하나만 출력한다. 두 나열은 앞에서부터 이름을 하나씩 사전순으로 비교하고, 처음으로 달라지는 위치가 순서를 정한다.