레이팅 미적용KOI 동물원에는 N마리의 원숭이가 있고, 이 원숭이들을 수용할 수 있는 두 개의 큰 우리가 있다. 모든 원숭이들은 1부터 N까지의 번호가 매겨져 있다.
원숭이들 사이에는 유달리 서로 앙숙관계인 원숭이들이 있어서 같은 우리에 두었을 경우 서로 싸우는 경우가 많다. 두 원숭이 x와 y가 앙숙관계라는 것은 두 원숭이 x, y가 서로 싫어하는 관계임을 의미한다. 또한, 각각의 한 원숭이에 대해 앙숙관계에 있는 원숭이들의 수는 기껏해야 세 마리라고 가정한다. 동물원에서는 원숭이들의 앙숙관계를 조사하여 아래의 두 조건을 만족하도록 원숭이들을 두 개의 우리에 나누어 수용하려고 한다.
(조건 1) 각 원숭이에 대해 같은 우리 안에 있으며 앙숙관계인 원숭이는 한 마리 이하이다.
(조건 2) 비어있는 우리는 없다. (즉, 하나의 우리에 원숭이를 모두 수용 가능한 경우가 있더라도 각각의 우리에는 적어도 한 마리 이상의 원숭이를 수용하여야 한다.)
예를 들어, \(N=5\) 인 경우에 1번 원숭이는 {2, 3, 4}와 2는 {1, 3, 5}와 앙숙관계이고, 그리고 3은 {1, 2, 4}와 4는 {1, 3, 5}, 그리고 5는 {2, 4}와 앙숙관계라고 하자. 위의 조건을 만족하도록 원숭이들을 두 개의 우리로 나누려면 {1, 3, 5}를 하나의 우리에, 그리고 {2, 4}를 다른 우리에 수용하면 된다.
원숭이들의 수와 각 원숭이들의 앙숙관계가 입력으로 주어질 때, 위의 조건을 만족하도록 원숭이들을 두 개의 우리에 나누어 수용하는 프로그램을 작성하시오.
※ 이 문제의 채점 데이터는 공개된 공식 데이터가 없어 재구성한 것입니다. 문제 지문은 원본(정보올림피아드 기출)을 따릅니다.
첫째 줄에는 원숭이들의 수를 나타내는 하나의 정수 N이 주어진다. 단, N은 3이상 100,000이하의 정수이다. 둘째 줄부터 N개의 줄에는 1번부터 번호순서대로 각 원숭이에 대해 앙숙관계에 있는 원숭이의 수 M이 주어지고, 이어서 각 원숭이 번호 M개가 오름차순으로 하나의 줄에 주어진다. 모든 정수들 사이에는 빈칸이 있다. 조건에 맞도록 원숭이들을 나누지 못하는 경우는 존재하지 않는다.
첫째 줄에는 하나의 우리에 수용되는 원숭이의 수와 원숭이들의 번호를 빈칸을 사이에 두고 임의의 순서대로 출력하고, 둘째 줄에는 또 다른 하나의 우리에 수용되는 원숭이의 수와 원숭이들의 번호를 빈칸을 사이에 두고 임의의 순서대로 출력한다. 만약, 조건에 맞게 원숭이들을 수용하는 경우가 여러 개일 경우에는 그 중의 하나를 출력한다.
5
3 2 3 4
3 1 3 5
3 1 2 4
3 1 3 5
2 2 4
2 2 4
3 1 3 5
6
1 2
1 1
0
1 5
2 4 6
1 5
3 2 4 6
3 1 3 5
생성자가 기록되지 않았습니다.
출처 올림피아드 > 한국정보올림피아드 > KOI 2012 > 2차 대회 > 중등부 4번