부서 배치

한 회사는 신입사원 N명을 두 개발 부서 A와 B에 배치하려고 한다. 직원들 사이에는 같은 부서에서 일해야 하는 친구 관계와 서로 다른 부서에서 일해야 하는 경쟁 관계가 있다.

두 직원 x, y가 친구 관계이면 +(x,y)로, 경쟁 관계이면 -(x,y)로 표시한다. 한 쌍의 직원이 두 관계를 동시에 가질 수는 없다. 두 관계는 모두 대칭적이므로 +(x,y)이면 +(y,x)도 성립하고, -(x,y)이면 -(y,x)도 성립한다.

올바른 부서 배치는 다음 조건을 모두 만족해야 한다.

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

신입사원이 {1,2,3}이고 관계가 아래 R1과 같으면 세 명을 모두 같은 부서에 넣을 수 있으므로 올바른 배치가 가능하다.

R2는 A={1,2}, B={3}처럼 배치할 수 있다. R3에서는 세 쌍이 모두 경쟁 관계라서 세 명을 두 부서에 나누면 어떤 경쟁 관계 한 쌍은 같은 부서에 놓일 수밖에 없다. R4에서도 친구 관계와 경쟁 관계 조건이 서로 충돌하므로 올바른 배치가 불가능하다.

신입사원이 4명일 때 아래 R5와 R6은 모두 올바른 배치가 가능하다. R5에서는 두 부서 인원수 차이의 최솟값이 2이고, R6에서는 두 부서 인원수가 같아져 차이가 0이다.

주어진 친구 관계와 경쟁 관계를 이용해, 각 검사용 데이터마다 올바른 부서 배치가 가능한지 판단하라.

입력은 항상 5개의 검사용 데이터로 이루어진다.

각 검사용 데이터의 첫 줄에는 신입사원의 수 N과 관계 자료의 수 M이 공백으로 구분되어 주어진다. 직원은 1부터 N까지의 정수로 번호가 매겨진다.

이후 M개의 줄에는 관계 하나가 1 x y 또는 -1 x y 형식으로 주어진다. 1 x y는 x와 y가 친구 관계임을, -1 x y는 x와 y가 경쟁 관계임을 뜻한다.

N과 M은 3 이상 10,000 이하의 정수이다.

5개의 검사용 데이터 각각에 대해 결과를 한 줄씩 출력한다.

올바른 부서 배치가 가능하면 가능한 배치 중 두 부서 인원수 차이의 최솟값을 음이 아닌 정수로 출력한다. 불가능하면 -1을 출력한다.