시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 88 26 20 31.250%

문제

게임업체인 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식 배치가 가능한지를 판단하는 프로그램을 작성해야 한다.

입력

이 파일에는 항상 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’을 출력한다. 

예제 입력

3 3
-1 1 2
-1 2 3
-1 3 1
4 4
-1 1 3
1 1 2
1 3 4
-1 4 2
7 8
1 1 2
1 2 3
1 3 1
-1 3 4
-1 2 5
1 5 6
1 6 7
1 5 7
3 3
1 1 3
1 1 2
-1 2 3
5 3
1 4 5
1 4 3
1 4 2

예제 출력

-1
0
1
-1
3

힌트