Strongly Matchable

$G$ is a simple undirected graph with $n$ vertices, and its vertex set and edge set are written $V(G)$ and $E(G)$. Two edges of $G$ are adjacent if they share a vertex. Two vertices of $G$ are adjacent if they share an edge, and that edge joins the two vertices. An edge and an endpoint of that edge are incident. A subset $M$ of $E(G)$ is a matching of $G$ if no two edges in $M$ are adjacent, and $M$ is a perfect matching if every vertex of $G$ is incident to exactly one edge of $M$. So a matching $M$ is perfect if and only if $|M| = n/2$.

A maximum matching, a matching with the largest number of edges, can be found in polynomial time, so the existence of a perfect matching in $G$ is decided in polynomial time. Two more questions can be asked about the existence of a perfect matching.

• Given one partition of $V(G)$ into $S$ and $T$ with $|S| = |T| = n/2$, does $G$ have a perfect matching in which every edge joins a vertex in $S$ and a vertex in $T$?
• For every partition of $V(G)$ into $S$ and $T$ with $|S| = |T| = n/2$, does $G$ have a perfect matching in which every edge joins a vertex in $S$ and a vertex in $T$?

Hall's marriage theorem gives a condition that characterizes the answer to the first question. Let $G'$ be the spanning subgraph of $G$ obtained by deleting every edge whose endpoints both lie in $S$ or both lie in $T$, so that $V(G') = V(G)$ and $E(G')$ is the set of all edges of $E(G)$ with one endpoint in $S$ and the other endpoint in $T$. Then $G$ has the required perfect matching between $S$ and $T$ if and only if $G'$ has a perfect matching. By Hall's theorem, $G'$ has a perfect matching if and only if $|N(X)| \ge |X|$ holds for every subset $X$ of $S$, where $N(X)$ is the neighborhood of $X$, the set of all vertices in $T$ adjacent to some vertex of $X$. A polynomial-time maximum matching algorithm answers this question in polynomial time as well.

Is there an efficient algorithm for the second question? A graph whose answer to the second question is yes is called strongly matchable. That is, $G$ is strongly matchable if, for every partition of $V(G)$ into $S$ and $T$ with $|S| = |T| = n/2$, $G$ has a perfect matching in which each edge joins one vertex in $S$ and one vertex in $T$. For example, the graph in figure 1 (a) is strongly matchable. Up to symmetry there are only three partitions, and each of them admits a perfect matching: $M = \{(1,4), (2,5), (3,6)\}$ for $S = \{1, 2, 3\}$ and $T = \{4, 5, 6\}$, $M = \{(1,3), (2,5), (4,6)\}$ for $S = \{1, 2, 4\}$ and $T = \{3, 5, 6\}$, and $M = \{(1,3), (2,5), (6,4)\}$ for $S = \{1, 2, 6\}$ and $T = \{3, 4, 5\}$. The graph in (b) is not strongly matchable, because there is no perfect matching between $S = \{1, 2, 4\}$ and $T = \{3, 5, 6\}$. Write a program that decides whether a graph with an even number of vertices is strongly matchable.

(a)	(b)

Figure 1: the graph in (a) is strongly matchable, and the graph in (b) is not.

The first line contains the number of vertices $n$ and the number of edges $m$. $n$ is even, $2 \le n \le 100$, and $1 \le m \le n(n-1)/2$. Each of the next $m$ lines contains one edge, given as the two vertices $u$ and $v$ that the edge joins. The vertices are indexed from $1$ to $n$. The input graph is simple, so it contains no loop and no repeated edge.

Print $1$ on one line if the input graph is strongly matchable, and $-1$ otherwise. The output is a single integer.