Nombre cromàtic W52152

Donat un graf no dirigit, una coloració d’aquest graf és una assignació de colors a cadascun dels vèrtexs del graf de forma que cap aresta tingui extrems del mateix color. El nombre cromàtic d’un graf és el mínim nombre de colors necesaris per colorar un graf donat.

Entrada

L’entrada conté diferents grafs. Cadascun comença amb n i m, corresponent al nombre de vèrtexs i arestes del graf. Segueixen m parells u, v, indicant que hi ha una aresta entre u i v. Es té que 1 ≤ n ≤ 9, que 0 ≤ m ≤ n(n−1)/2, que 0 ≤ u < v <n i que no hi ha arestes repetides.

Sortida

Per a cada graf, escriviu el seu nombre cromàtic.