게임업체인 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 한쪽 부서로 전부 배치하면 되기 때문이다.

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

실행시간은 1초를 넘을 수 없으며, 부분 점수는 없다.

입력 형식

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

부분 점수는 검사용 데이터의 5개 모두에 대해서 부서배치 여부를 맞춘(즉, 불가능한 경우 -1, 가능한 경우 0 이상의 값을 출력) 경우에만 주어진다.(더블릿에서는 불필요)

입력과 출력의 예

입력 

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

출처:koi 2011 전국본선 고등부 2번
문제작업:tncks0121