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}를 다른 우리에 수용하면 된다.

원숭이들의 수와 각 원숭이들의 앙숙관계가 입력으로 주어질 때, 위의 조건을 만족하도록 원숭이들을 두 개의 우리에 나누어 수용하는 프로그램을 작성하시오.

#2585 upload 446 done 86 how_to_reg 62 auto_awesome 스페셜 저지

원숭이 timer 1s memory 64MB

#2585
스페셜 저지

원숭이 1s 64MB