링커

컴퓨터 프로그램은 보통 여러 개의 모듈로 이루어지며, 이러한 프로그램의 컴파일은 대개 두 단계로 진행된다.

먼저 각 소스 모듈은 독립적으로 컴파일되어 하나의 오브젝트 모듈이 된다. 오브젝트 모듈은 세 부분으로 구성된다.

• 컴파일된 프로그램 코드,
• 익스포트 테이블(export table),
• 임포트 테이블(import table).

익스포트 테이블에는 이 모듈이 정의하며 다른 모듈이 사용할 수 있는 심볼(예: 변수나 함수 이름)들이 나열된다. 임포트 테이블에는 이 모듈이 의존하는 외부 심볼들이 나열된다.

모든 모듈이 컴파일된 뒤, 링커(linker)라는 프로그램이 이들을 하나의 실행 파일로 결합한다.

모든 프로그램에는 실행이 시작되는 지점인 진입점(entry point)이 있다. 진입점은 하나의 심볼이며, 진입점을 "포함하는" 모듈이란 그 심볼을 익스포트하는 모듈을 뜻한다. 링커는 실행 파일을 더 작게 만들기 위해, 진입점을 포함하는 모듈과 그 모듈이 직접 또는 간접적으로 의존하는 모든 모듈만을 남긴다. 나머지 모듈은 불필요한(redundant) 모듈이라고 부른다.

의존 관계는 심볼을 통해 정의된다. 어떤 모듈이 다른 모듈이 익스포트하는 심볼을 임포트하면, 앞의 모듈은 뒤의 모듈에 의존한다. 하나의 심볼이 여러 모듈에서 익스포트된다면, 그 심볼을 임포트하는 모듈은 그 모든 모듈에 의존한다.

각 모듈의 정보가 주어졌을 때 다음을 구하여라.

• 불필요하지 않은(non-redundant) 모든 모듈,
• 모든 중복 익스포트(duplicate export): 두 개 이상의 모듈에서 익스포트되면서, 불필요하지 않은 모듈 중 적어도 하나가 임포트하는 심볼,
• 모든 해결되지 않은 임포트(unresolved import): 불필요하지 않은 모듈 중 적어도 하나가 임포트하지만, 어떤 모듈에서도 익스포트되지 않는 심볼.

진입점 심볼이 어떤 모듈에서도 익스포트되지 않는다면, 그 심볼 역시 해결되지 않은 임포트로 취급한다. 이 경우 진입점을 포함하는 모듈이 없으므로 불필요하지 않은 모듈도 존재하지 않는다.

첫째 줄에는 진입점의 이름이 주어진다.

둘째 줄에는 모듈의 수 $N$ ($1 \le N \le 100$)이 주어진다.

그 다음에는 각 모듈을 설명하는 $N$개의 블록이 이어진다.

• 블록의 첫째 줄에는 모듈의 이름이 주어진다.
• 다음 줄에는 익스포트의 수 $E$ ($0 \le E \le 100$)가 주어지고, 이어서 $E$개의 줄에 서로 다른 익스포트 심볼이 한 줄에 하나씩 주어진다.
• 다음 줄에는 임포트의 수 $I$ ($0 \le I \le 100$)가 주어지고, 이어서 $I$개의 줄에 서로 다른 임포트 심볼이 한 줄에 하나씩 주어진다.

이 문제에 등장하는 모든 이름은 라틴 문자와 숫자로 이루어진, 길이가 최대 $30$인 비어 있지 않은 문자열이다.

불필요하지 않은 모듈, 중복 익스포트, 해결되지 않은 임포트를 차례로 출력한다. 답이 유일하도록, 각 그룹을 다음의 정해진 순서로 출력한다.

• 먼저 불필요하지 않은 모듈의 수 $M_R$을 출력하고, 이어서 $M_R$개의 줄에 그 모듈들의 이름을 입력에 등장한 순서대로 출력한다.
• 다음으로 중복 익스포트 심볼의 수 $M_E$를 출력하고, 이어서 $M_E$개의 줄에 그 심볼들을 ASCII 오름차순으로 출력한다.
• 다음으로 해결되지 않은 임포트 심볼의 수 $M_I$를 출력하고, 이어서 $M_I$개의 줄에 그 심볼들을 ASCII 오름차순으로 출력한다.

ASCII 순서에서는 숫자가 대문자보다 앞서고, 대문자가 소문자보다 앞선다.