명제 증명
면접 대비시간 제한2초메모리 제한128 MB
문자들 간의 방향 관계가 주어질 때 전이 폐쇄를 구해 자기 자신을 제외한 증명 가능한 명제들을 정렬해 출력합니다.
문제
수학과 논리학에서는 "P이면 Q이다"와 같은 꼴의 명제가 자주 쓰인다. 이 명제는 보통 P => Q로 나타낸다. 여기서 P는 전건, Q는 후건이다.
두 명제 P => Q와 Q => R이 모두 참이면, 삼단 논법에 따라 P => R도 참이다. 이 문제에서는 주어진 참인 명제들과 이 규칙만을 이용해 증명할 수 있는 명제를 찾는다.
입력으로 주어진 명제는 그 자체로 이미 참이므로 증명된 것으로 본다. 단, P => P처럼 전건과 후건이 같은 명제는 항상 참이지만 출력하지 않는다.
N개의 참인 명제가 주어졌을 때, 증명할 수 있는 모든 명제를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정수 N (1 <= N <= 10,000)이 주어진다. 다음 N개의 줄에는 참인 명제가 하나씩 주어진다.
각 명제는 P => Q 형식이며, =>의 앞뒤에는 공백이 하나씩 있다. P와 Q는 알파벳 대문자 또는 소문자 한 글자이다. 같은 명제가 여러 번 주어질 수 있다.
출력
첫째 줄에 출력할 명제의 개수 X를 출력한다. 다음 X개의 줄에는 증명할 수 있는 명제를 하나씩 출력한다.
출력 순서는 전건의 알파벳 순이며, 전건이 같으면 후건의 알파벳 순이다. 알파벳 순서는 A, B, ..., Z, a, b, ..., z이다. 전건과 후건이 같은 명제는 출력하지 않는다.