강강술래

강강술래에 참여하기를 원하는 학생이 명 있다. 각 학생은 1번부터 번까지 서로 다른 번호가 붙어 있다. 감독은 이 학생들 중에서 한 그룹의 학생을 선정하여 강강술래 춤을 추게 하려고 한다. 감독은 학생들에게 자신이 강강술래를 출 때 옆에 춤추기를 원하는 학생의 번호 하나를 제출하도록 하였고, 또한 같이 춤추기를 원하지 않는 학생이 있는 경우 한 학생의 번호를 제출하도록 하였다. 학생들이 제출한 리스트를 보고 감독은 가장 규모가 큰 ‘양호한 그룹’을 찾기로 하였다. 아래 조건을 모두 만족하는 학생들의 그룹 를 ‘양호한 그룹’이라고 한다.

에 속한 학생의 수는 둘 혹은 그 이상이다.

에 속한 학생의 수를 이라고 할 때, 에 속한 학생들을 다음 조건을 만족하도록  과 같이 원형으로 세울 수 있어야 한다: 모든 에 대하여 학생 는 학생 이 옆에서 춤추기를 원하며, 학생 은 학생 이 옆에서 춤추기를 원한다.

에 속한 학생 각각에 대해서, 에 속하면서 그 학생과 같이 춤추기를 원하지 않는 학생의 수는  보다 작다. (실수 에 대해서 는 와 같거나 큰 정수 중에서 가장 작은 것을 말한다.)

예를 들어, 학생 1은 학생 2가 옆에서 춤추기를 원하고, 학생 2는 학생 3이, 학생 3은 학생 4가, 학생 4는 학생 1이, 학생 5는 학생 6이, 학생 6은 학생 5가 옆에서 춤추기를 원한다고 하자. 또한 학생 1, 2는 학생 4와 같이 춤추기를 원하지 않고 학생 5, 6은 학생 1과 같이 춤추기를 원하지 않는다고 하자. 그룹 {1, 2, 3, 4}는 위 조건 (1)과 (2)를 만족하지만, 조건 (3)를 만족하지 않으므로, 가장 규모가 큰 양호한 그룹은 {5, 6}이다.

학생들이 제출한 리스트를 보고 가장 규모가 큰 양호한 그룹을 찾는 프로그램을 작성하시오. 프로그램 이름은 dance.cpp, 실행 파일의 이름은 dance.exe, 프로그램 설명 파일 이름은 dance.hwp로 하고, 프로그램의 실행시간은 1초를 초과할 수 없다. 부분 점수는 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT로 한다. 첫째 줄에 학생들의 수 이 주어진다. 둘째 줄부터 마지막 줄까지 번째 줄에는 학생 가 옆에서 춤추기를 원하는 학생 번호 에 이어서 같이 춤추기를 원하지 않는 학생 번호 가 빈칸을 사이에 두고 주어진다. 같이 춤추기를 원하지 않는 학생이 없을 경우 는 -1과 같다.

2004 가을학기 문제해결기법	문제 #10

출력 형식

출력 파일의 이름은 OUTPUT.TXT로 한다. 한 줄에 가장 규모가 큰 양호한 그룹의 크기, 즉 그룹에 속한 학생의 수를 출력한다. 양호한 그룹이 존재하지 않으면 -1을 출력한다.

입력과 출력의 예

입력(input.txt)

6

2 4

3 4

4 -1

1 -1

6 1

5 1

출력(output.txt)

2