시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 2 2 2 100.000%

문제

어제 자유시간에 혼자 위닝을 하면서 자신의 실력을 자랑하던 주호는 강조교한테 편안하게 버스를 타고 말았다.

이에 화가 난 주호는 공부에 대한 생각도 잊은채 위닝을 연습하기로 결심하였다. 하지만 수업시간에 컴퓨터로 직접 하는것이 힘들었기 때문에 바깥에서 N개의 돌멩이로 전략을 세우기로 결심하였다.

주호는 연구한 끝에 자신의 가장 큰 약점은 패스라는 것을 깨달았다. 결국 적절하게 돌멩이를 배치한 다음 효율적으로 패스하는 법을 연구하기로 했는데….

N개의 돌멩이들이 있고  상호간에 패스가 가능한 쌍들이 있다. 즉 모든 쌍들 사이에 패스가 가능한 것이 아니다.

주호는 이 돌멩이들을 적절하게 공격 그룹과 수비 그룹의 두 그룹으로 나누고자 한다. 하지만 패스가 효율적으로 이루어지기 위해서는 각각의 돌멩이들에 대해, 자신과 같은 그룹에 속해 있으면서 패스가 가능한 돌멩이들의 수가 짝수가 되어야 한다. 결국 주호의 목적은 이 조건을 만족하는 총 돌멩이의 숫자가 최대 몇 개인지 알아내는 것이다.

입력

첫 번째 줄에 돌멩이의 개수 N(1 <= N <= 200)이 주어진다. 그 다음 i+1번째 줄에 i번째 돌멩이가 패스할 수 있는 돌멩이의 개수 Li가 들어온다. 그리고 그 다음 각각의 줄에 Li개의 패스 가능한 돌멩이에 해당하는 숫자가 들어온다. 단 각각의 돌멩이들이 자신에게 패스하는 경우는 없고, A 돌멩이가 B 돌멩이의 패스가 가능하다면 B도 A에게 패스가 가능하다고 하자.

출력

첫 번째 줄에 공격이나 수비 중 한쪽 그룹에 속한 돌멩이의 개수 M이 출력된다. 그리고 그 다음 줄에 그 그룹에 속한 돌멩이에 해당하는 숫자를 출력한다. 출력되지 않은 숫자는 반대편 그룹에 속하는 것으로 한다. 여러 가지 해가 존재하는 경우 그 중 하나만 출력하면 된다.

예제 입력

5
3 2 3 4
2 1 3
4 2 1 4 5
2 1 3
1 3

예제 출력

3
1 2 3

힌트

출처

Olympiad > Polish Olympiad in Informatics > POI 2004/2005 > Stage 3 3번

  • 문제를 번역한 사람: author6
  • 스페셜 저지를 만든 사람: koosaga