Graf hamiltonià? P36190

Un graf no dirigit es diu hamiltonià si conté almenys un cicle que passi exactament una vegada per cada vèrtex. Recordeu que un cicle és un camí que comença i acaba en el mateix vèrtex, i que no repeteix cap altre vèrtex ni passa més d’una vegada per cap aresta.

Donada una n, construïm un graf amb vèrtexs 2, 3, …, n, i connectem entre si els que són coprimers. És a dir, per a cada dos vèrtexs x i y, existirà una aresta que els connecti sii mcd(x, y) = 1. Per exemple, aquest és el graf per a n = 5:

Donada una n, podríeu dir si el graf corresponent és hamiltonià?

Entrada

L’entrada conté diversos casos, cadascun amb una n entre 3 i 10⁴.

Sortida

Escriviu una línia per a cada cas. Si el graf no és hamiltonià, escriviu “NO”. Altrament, escriviu “SI” seguit de qualsevol cicle hamiltonià. Cal escriure tots els vèrtexs del cicle, amb l’inici igual al final. Seguiu estrictament el format dels exemples.