부서 배치 timer 1초 memory 128MB

게임업체인 KOI (Kernel Operation International)는 2011년 신입사원을 두 개의 개발부서 A, B에 적절히 나누어서 배치하려고 한다. 그런데 사원들 중에는 같이 일을 하고 싶어 하는 “친구관계”인 사람들과 같은 부서에서 일하기를 싫어하는 “경쟁관계”인 사람들이 있다.

x와 y가 친구 관계이면 +(x,y)로 표시하고, 경쟁관계이면 -(x,y)로 표시한다. 단 두 사람 x와 y가 +(x,y)와 -(x,y)를 동시에 만족할 수는 없다. 그리고 친구관계와 경쟁관계에는 대칭성이 있어서 +(x,y)이면 +(y,x)도 성립하고, -(x,y)이면 -(y,x)도 항상 성립된다.

신입사원 전체를 A, B 두 부서에 배치하는 KOI식 배정 원칙은 다음과 같다.

1) 모든 신입사원은 두 부서 중 한 부서에는 반드시 배치되어야 한다. 2) +(x,y)관계인 x와 y는 반드시 같은 부서에 배치되어야 한다. 3) -(x,y)관계인 x와 y는 반드시 서로 다른 부서에 배치되어야 한다. 4) 두 부서 A와 B에 배정된 인원수의 차이는 최소가 되어야 한다.

  3명의 신입사원 {1,2,3}이 있고 이들의 관계가 다음 표의 R1과 같다면 이들은 KOI식 배치가 가능하다. 왜냐하면 {1,2,3} 모두를 A나 B 한쪽 부서로 전부 배치하면 되기 때문이다.

R2의 경우라면 A={1,2} B = {3}로 배치할 수 있다. 그런데 R3의 경우라면 경쟁관계인 어떤 두 사람은 같은 부서에 배치될 수밖에 없으므로 KOI식 배치가 불가능하다. R4의 경우도 KOI식 배치가 불가능한데, A={1,2}, B={3}로 배치하면 친구관계인 2와 3이 다른 부서에 배치되고, A={2,3}, B={1}로 나누면 친구관계인 1과 2가 서로 다른 부서로 분리 배치되기 때문이다.

신입사원이 4명인 경우를 생각해보자. 이 경우 아래 R5나 R6의 경우에는 모두 KOI식 배치는 가능하다. R5의 경우 KOI식 배치를 하면 양쪽 부서원의 차이는 2명이며, R6의 경우 그 두 부서원의 차이는 0, 즉 두 부서의 인원은 같다.

여러분은 주어진 친구, 경쟁관계 데이터를 이용해서 KOI식 배치가 가능한지를 판단하는 프로그램을 작성해야 한다.