Maximum matching P59669

Given an undirected graph with $n$ vertices, a matching is a subset of the edges with no common vertices. Write a program to tell if a given graph has a maximum matching, that is, a grouping of the vertices in $n/2$ pairs such that all vertices belong to some pair, and that both vertices of every pair are directly connected.

Input

Input consists of several cases. Each case begins with $n$ and the number of edges $m$, followed by $m$ pairs of vertices. Assume $2 \le n \le 20$, that $n$ is even, that vertices are numbered from 1 to $n$, that there are no repeated edges nor edges connecting a vertex to itself, and that there is no isolated vertex.

Output

For every case, tell if the given graph has a maximum matching.

Observation

There are polynomial-time algorithms, more or less complicated, to solve this problem. Here, we settle for a simple backtracking.