우정 그래프

사람들이 서로 교류하는 집합이 주어졌을 때, 사람을 정점으로 하고 두 사람이 서로 친구일 때에만 간선이 있는 그래프를 생각할 수 있다. 이런 그래프를 소셜 네트워크라고 부르며, 대학의 학생들이나 작은 마을의 주민들과 같은 임의의 사람 집합에 대해 정의할 수 있다. 소셜 네트워크를 분석하는 학문이 최근 몇 년 사이에 등장했는데, 사람과 그들의 행동에서 흥미로운 여러 측면이 이 우정 그래프의 성질로 가장 잘 이해되기 때문이다.

Problem Solving 수업의 학생들을 정점으로 하는 우정 그래프가 주어졌을 때, 학생들을 두 그룹 $A$와 $B$로 나누어 다음 세 조건을 동시에 만족시키는 프로그램을 작성하시오.

• 수업의 각 학생은 정확히 하나의 그룹 $A$ 또는 $B$에 속한다.
• 각 그룹의 임의의 두 학생은 서로 친구이다.
• 그룹 $A$와 $B$의 크기 차이 $||A| - |B||$가 가능한 한 작다.

예를 들어 아래 그림과 같은 우정 그래프가 주어졌다고 하자. 학생들을 $A = \{u\_1, u\_2, u\_3, u\_6\}$과 $B = \{u\_4, u\_5, u\_7\}$로 나누는 것은 $u\_2$와 $u\_6$이 친구가 아니므로 불가능하다. 한편 $A = \{u\_1, u\_2\}$와 $B = \{u\_3, u\_4, u\_5, u\_6, u\_7\}$로 나누면 각 그룹의 임의의 두 학생은 서로 친구이지만, 두 그룹의 크기 차이($|2 - 5| = 3$)는 $A = \{u\_1, u\_2, u\_3\}$과 $B = \{u\_4, u\_5, u\_6, u\_7\}$로 나누었을 때의 차이($|3 - 4| = 1$)보다 크다. 마지막 분할이 우리가 원하는 최적의 분할이다.

프로그램은 표준 입력에서 데이터를 읽는다. 첫째 줄에는 우정 그래프의 정점 수와 간선 수를 나타내는 두 정수 $n$과 $m$이 주어지며, $2 ≤ n ≤ 1,000$이고 $0 ≤ m ≤ \binom{n}{2}$이다. 정점에는 $1$부터 $n$까지 번호가 매겨진다. 다음 $m$개 줄에는 각각 그래프의 간선 $(u, v)$를 나타내는 두 정수 $u$와 $v$가 주어진다.

프로그램은 표준 출력에 결과를 쓴다. 정수 하나를 포함하는 줄을 정확히 하나 출력한다. 이 정수는 학생들을 위 세 조건을 만족하도록 두 그룹으로 나눌 수 있을 때 두 그룹의 크기 차이의 최솟값이고, 그렇지 않으면 -1이다.