강하게 매칭 가능한 그래프

$G$는 정점이 $n$개인 단순 무향 그래프이고, 정점 집합과 간선 집합을 각각 $V(G)$, $E(G)$로 쓴다. 두 간선이 정점 하나를 공유하면 두 간선은 인접하다고 한다. 두 정점이 간선 하나를 공유하면 두 정점은 인접하다고 하고, 그 간선은 두 정점을 잇는다. 간선과 그 간선의 끝점은 서로 결합한다고 한다. $E(G)$의 부분집합 $M$에서 어떤 두 간선도 인접하지 않으면 $M$을 $G$의 매칭이라 한다. $G$의 모든 정점이 $M$의 간선 정확히 하나와 결합하면 $M$을 완전 매칭이라 한다. 곧 매칭 $M$이 완전 매칭인 것과 $|M| = n/2$인 것은 같은 말이다.

간선이 가장 많은 매칭을 찾는 다항 시간 알고리즘이 있으므로 $G$에 완전 매칭이 있는지는 다항 시간에 판정한다. 완전 매칭의 존재를 두고 다음 두 질문도 던질 수 있다.

• $|S| = |T| = n/2$인 $V(G)$의 분할 $S$, $T$ 하나가 주어졌을 때, 모든 간선이 $S$의 정점과 $T$의 정점을 잇는 완전 매칭이 $G$에 있는가?
• $|S| = |T| = n/2$인 $V(G)$의 모든 분할 $S$, $T$에 대해, 모든 간선이 $S$의 정점과 $T$의 정점을 잇는 완전 매칭이 $G$에 있는가?

첫 번째 질문의 답을 특징짓는 조건은 홀의 결혼 정리에서 끌어낼 수 있다. 양 끝점이 모두 $S$에 있거나 모두 $T$에 있는 간선을 지운 $G$의 신장 부분그래프를 $G'$라 하자. 곧 $V(G') = V(G)$이고, $E(G')$는 한 끝점이 $S$에 있고 다른 끝점이 $T$에 있는 $E(G)$의 간선을 모두 모은 집합이다. 그러면 $S$와 $T$를 잇는 완전 매칭이 $G$에 있는 것과 $G'$에 완전 매칭이 있는 것은 같은 말이다. 또 홀의 정리에서, $G'$에 완전 매칭이 있는 것은 $S$의 모든 부분집합 $X$에 대해 $|N(X)| \ge |X|$가 성립하는 것과 같다. 여기서 $N(X)$는 $X$의 어떤 정점과 인접한 $T$의 정점을 모두 모은 $X$의 이웃 집합이다. 최대 매칭 알고리즘이 다항 시간에 끝나므로 이 질문에도 다항 시간에 답한다.

두 번째 질문에는 효율적인 알고리즘이 있을까? 두 번째 질문의 답이 참인 그래프를 강하게 매칭 가능하다고 한다. 곧 $|S| = |T| = n/2$인 $V(G)$의 모든 분할 $S$, $T$에 대해 각 간선이 $S$의 정점 하나와 $T$의 정점 하나를 잇는 완전 매칭이 $G$에 있으면 $G$는 강하게 매칭 가능하다. 예를 들어 그림 1의 (a)는 강하게 매칭 가능하다. 대칭인 경우를 빼면 분할이 세 가지뿐이고 셋 다 완전 매칭이 있다. $S = \{1, 2, 3\}$, $T = \{4, 5, 6\}$에는 $M = \{(1,4), (2,5), (3,6)\}$, $S = \{1, 2, 4\}$, $T = \{3, 5, 6\}$에는 $M = \{(1,3), (2,5), (4,6)\}$, $S = \{1, 2, 6\}$, $T = \{3, 4, 5\}$에는 $M = \{(1,3), (2,5), (6,4)\}$가 있다. 그러나 (b)는 $S = \{1, 2, 4\}$와 $T = \{3, 5, 6\}$ 사이에 완전 매칭이 없으므로 강하게 매칭 가능하지 않다. 정점 수가 짝수인 그래프가 주어질 때 그 그래프가 강하게 매칭 가능한지 판정하는 프로그램을 작성하라.

(a)	(b)

그림 1: (a)는 강하게 매칭 가능하고, (b)는 그렇지 않다.

첫 줄에 정점 수 $n$과 간선 수 $m$이 주어진다. $n$은 짝수이고 $2 \le n \le 100$이며, $1 \le m \le n(n-1)/2$이다. 다음 $m$개 줄에는 간선이 하나씩 주어지고, 각 줄에는 그 간선이 잇는 두 정점 $u$와 $v$가 주어진다. 정점 번호는 $1$부터 $n$까지이다. 입력 그래프는 단순 그래프여서 자기 자신을 잇는 간선이 없고 같은 간선이 두 번 주어지지 않는다.

입력 그래프가 강하게 매칭 가능하면 $1$을, 그렇지 않으면 $-1$을 한 줄에 출력한다. 출력은 정수 하나뿐이다.