2001년 가을학기 문제해결기법 - 문제 12

분배 리스트

오늘은 교육부에서 2003학년도 대학 입시에 대한 회의가 열렸다. 이 회의에 교육부 입시 정책 관계자와 여러 대학의 입시 관계자들이 참석하였다. 그러나 모든 대학의 입시 관계자가 참석한 것은 아니다. 이 회의에 참석한 입시 관계자들에게는 회의 관련 자료를 담은 CD가 배포되었다.

문제는 이 회의에 참석하지 않은 대학에 입시 자료를 어떻게 전달하는 것이다. 이 문제를 해결하기 위해서 컴퓨터 네트워크를 이용하기로 결정하였다. 다행히 대학들은 네트워크로 서로 연결되어 있다. 그리고 각 대학은 이런 자료를 보낼 수 있도록 몇몇 다른 대학의 주소를 가지고 있다. 이 리스트를 분배 리스트라고 한다.

입시 자료를 받은 대학은 각 대학이 가지고 있는 분배 리스트에 있는 대학 중 아직 입시 자료를 받지 못한 대학에 무조건 입시 자료를 보낸다고 할 때, 어떤 대학에 입시 자료가 전달될 수 있고 어떤 대학은 가능하지 않는지를 알기를 원한다.

오늘 회의에 참석한 대학과 각 대학의 분배 리스트가 주어져 있을 때, 회의에서 제안된 방식으로 입시 자료를 받을 수 없는 대학을 모두 구하는 프로그램을 작성하시오.

프로그램명은 list.cpp(list.c)라고 하고 실행 파일명은 list.exe로 한다. 프로그램의 실행 시간은 5초를 초과할 수 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT이다. 첫째 줄에 회의에 참석한 대학의 수 [eqn: n]이 입력된다. 모든 대학은 [eqn: 1]번부터 [eqn: n]번까지 번호가 붙어 있고, [eqn: n]은 200이하이다. 둘째 줄부터 [eqn: n]개의 줄에는 한 줄에 한 대학의 분배 리스트가 입력된다. [eqn: i]번 대학의 분배 리스트는 [eqn: i+1]번째 줄에 입력된다. 각 대학의 분배 리스트를 나타내기 위해서 리스트에 속한 대학의 수, 그리고 리스트에 속한 대학의 번호가 차례로 주어진다. [eqn: n+2]번째 줄에는 오늘 회의에 참석한 대학의 수 [eqn: k]와 대학의 번호가 차례로 입력된다. 각 줄에 하나 이상의 숫자가 입력되는 경우 이들 숫자 사이에 공백이 있다.

출력 형식

출력 파일의 이름은 OUTPUT.TXT이다. 첫째 줄과 둘째 줄에 각각 입시 자료가 분배될 수 없는 대학의 수와 리스트를 출력한다. 대학 리스트를 출력할 때는 반드시 번호가 증가하는 순서로 출력한다. 첫째 줄의 출력이 0인 경우는 둘째 줄을 출력하지 않는다.

입력과 출력의 예

INPUT.TXT

10

2 2 3

2 3 7

1 4

1 1

1 6

1 7

1 5

1 9

1 10

2 2 8

2 1 2

OUTPUT.TXT

3

8 9 10