원숭이
시간 제한1초메모리 제한128 MB
최대 차수가 3인 그래프의 정점을 두 개의 비어있지 않은 그룹으로 나누어 각 정점이 같은 그룹에서 자신을 싫어하는 정점을 최대 하나만 갖도록 분할합니다.
문제
동물원에 1번부터 N번까지 번호가 붙은 원숭이 N마리가 있다. 동물원에는 원숭이를 나누어 넣을 수 있는 큰 우리가 두 개 있다.
일부 원숭이 쌍은 서로 사이가 좋지 않다. 서로 사이가 좋지 않은 두 원숭이를 같은 우리에 넣으면 싸울 수 있다. 각 원숭이와 사이가 좋지 않은 원숭이는 최대 세 마리이다.
원숭이들을 두 우리에 나누어 넣되, 다음 조건을 모두 만족해야 한다.
- 각 원숭이에 대해, 같은 우리 안에 있으면서 그 원숭이와 사이가 좋지 않은 원숭이는 한 마리 이하여야 한다.
- 두 우리 모두 비어 있으면 안 된다.
원숭이 수와 서로 사이가 좋지 않은 관계가 주어질 때, 조건을 만족하는 배치를 하나 구하시오.
입력
첫째 줄에 원숭이의 수 N이 주어진다. N은 3 이상 100,000 이하의 정수이다.
다음 N개의 줄에는 1번 원숭이부터 N번 원숭이까지 차례대로 정보가 주어진다. 각 줄에는 먼저 그 원숭이와 사이가 좋지 않은 원숭이의 수 M이 주어지고, 이어서 해당 원숭이들의 번호 M개가 오름차순으로 주어진다. 모든 정수는 공백으로 구분된다.
조건을 만족하는 배치가 항상 존재하는 입력만 주어진다.
출력
두 줄을 출력한다.
첫째 줄에는 한 우리에 들어가는 원숭이의 수와 그 원숭이들의 번호를 공백으로 구분해 출력한다. 둘째 줄에는 다른 우리에 들어가는 원숭이의 수와 그 원숭이들의 번호를 공백으로 구분해 출력한다.
번호의 순서는 임의로 정해도 된다. 가능한 배치가 여러 가지라면 그중 아무거나 출력해도 된다.