Definition 1 A graph G = (V, E) is called “dense” if for each pair of non-adjacent vertices u and v, d(u) + d(v) ≥ n where n = |V | and d(•) denotes the degree of the vertex •. Definition 2 A “Hamiltonian cycle” on G is a sequence of vertices (vi1 vi2 . . . vin vi1 ) such that vi ̸= vi lh foralll̸=hand{vi ,vi }isanedgeofG. l l+1 The problem is: write a program that, given a dense indirect graph G = (V; E) as input, deter- mines whether G admits a Hamiltonian cycle on G and outputs that cycle, if there is one, or outputs ‘N’ if there is none. Input The input file contains several descriptions of graphs (each one ending with a ‘%’), in the form: n1 ui1 uj1 ui2 uj2 ... % n2 ui1 uj1 ui2 uj2 ... % where ni is the number of vertices (0 < ni ≤ 256) and uih uil are integers between 1 and ni indicating that there exists an edge between vertex uih and uil Output For each test case, output a line that must contain the sequence of vertices that form a Hamiltonian cycle in the form: ui1 ui2 ui3 ... or containing: N Sample Input 4 12 23 24 34 31 %
775 – Hamiltonian Cycle 2/2 6 12 13 16 32 34 52 54 65 64 % Sample Output 12431 1325461