게임업체인 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식 배정 원칙은 다음과 같다.

• 모든 신입사원은 두 부서 중 한 부서에는 반드시 배치되어야 한다.

• +(x,y) 관계인 x와 y는 반드시 같은 부서에 배치되어야 한다.

• -(x,y) 관계인 x와 y는 반드시 서로 다른 부서에 배치되어야 한다.

• 두 부서 A와 B에 배정된 인원수의 차이는 최소가 되어야 한다.

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

        R1
        R2
        R3
        R4





        +(1,2)



        +(2,3)



        +(1,3)




        +(1,2)



        -(2,3)



        -(3,1)




        -(1,2)



        -(2,3)



        -(3,1)




        +(1,2)



        +(2,3)



        -(3,1)

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, 즉 두 부서의 인원은 같다.

        R5
        R6





        +(1,2)



        +(2,3)




        +(1,2)



        +(3,4)

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

※ 이 문제의 채점 데이터는 공개된 공식 데이터가 없어 재구성한 것입니다. 문제 지문은 원본(정보올림피아드 기출)을 따릅니다.

이 파일에는 항상 5개의 검사용 데이터가 주어진다.

각 검사용 데이터의 첫 줄에는 신입사원의 수 N, 그리고 친구 또는 경쟁 관계를 나타내는 자료의 수 M이 하나의 공백을 두고 나타난다.

이 문제에서 N명의 신입사원은 정수 1, 2,3,..., N으로 표시된다. 그리고 이어지는 M개의 줄에는 +(x,y)와 -(x,y)의 관계가 각각 '1 x y' 과 '-1 x y' 의 형식으로 주어진다. N과 M은 3 이상 10,000 이하의 정수이다.

입력 파일에 제시된 5개의 검사용 데이터에 대하여 KOI식 부서배치가 가능한지를 계산하여 그 결과를 5개의 줄에 각각 출력한다. 만일 KOI식 배치가 가능하면 두 부서 인원의 차이를 나타내는 음이 아닌 정수 값을 출력하고, 만일 KOI식 배치가 불가능하면 음수 ‘-1’을 출력한다.

생성자가 기록되지 않았습니다.

출처 올림피아드 > 한국정보올림피아드 > KOI 2011 > 2차 대회 > 고등부 2번