원숭이 |
---|
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개가 오름차순으로 하나의 줄에 주어진다. 모든 정수들 사이에는 빈칸이 있다. 조건에 맞도록 원숭이들을 나누지 못하는 경우는 존재하지 않는다. |
출력 | |
---|---|
첫째 줄에는 하나의 우리에 수용되는 원숭이의 수와 원숭이들의 번호를 빈칸을 사이에 두고 임의의 순서대로 출력하고, 둘째 줄에는 또 다른 하나의 우리에 수용되는 원숭이의 수와 원숭이들의 번호를 빈칸을 사이에 두고 임의의 순서대로 출력한다. 만약, 조건에 맞게 원숭이들을 수용하는 경우가 여러 개일 경우에는 그 중의 하나를 출력한다. |
예시 | |||
---|---|---|---|
1 | 입력 | 5 3 2 3 4 3 1 3 5 3 1 2 4 3 1 3 5 2 2 4 | |
출력 | 3 1 3 5 2 2 4 |