Aparellament màxim P59669

Donat un graf no dirigit amb $n$ vèrtexs, un aparellament és un subconjunt de les arestes sense cap vèrtex en comú. Feu un programa que digui si un graf donat té un aparellament màxim, és a dir, un agrupament dels vèrtexs en $n/2$ parells de manera que tots els vèrtexs estiguin en algun parell, i que els dos vèrtexs de cada parell estiguin connectats directament.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb $n$ i el nombre d’arestes $m$, seguits de $m$ parells de vèrtexs. Suposeu $2 \le n \le 20$, que $n$ és parell, que els vèrtexs es numeren de 1 a $n$, que no hi ha arestes repetides ni connectant un vèrtex amb ell mateix, i que no hi ha cap vèrtex de grau zero.

Sortida

Per a cada cas, digueu si el graf té algun aparellament màxim.

Observació

Hi ha algorismes polinòmics, més o menys complicats, per resoldre aquest problema. Aquí, ens conformem amb un simple backtracking.