Hamiltonian Cycle 

A few definitions first:

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) \ge n$ where n = |V| and $d(\bullet)$ denotes the degree of the vertex $\bullet$.

Definition 2

A ``Hamiltonian cycle'' on G is a sequence of vertices ( $v_{i_1} v_{i_2} \dots v_{i_n} v_{i_1}$) such that $v_{i_l} \neq v_{i_h}$ for all $l \neq h$ and { v_il, v_il} is an edge of G.

The problem is: write a program that, given a dense 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 

A file containing descriptions of graphs, each one ending with a %, in the form:

n₁

$u_{i_1} \ u_{j_1}$

$u_{i_2} \ u_{j_2}$

$\dots$

%

n₂

$u_{i_1} \ u_{j_1}$

$u_{i_2} \ u_{j_2}$

$\dots$

%

where n_i is the number of vertices and $u_{i_h} \ u_{i_l}$ are integers between 1 and n indicating that there exists an edge between vertex u_ih and u_il

Output 

The output file must contain the sequence of vertices that form a Hamiltonian cycle in the form:

$u_{i_1} \ u_{i_2} \ u_{i_3 } \ \dots$

or containing:

N

Sample Input 

4
1 2
2 3
2 4
3 4
3 1
%
6
1 2
1 3
1 6
3 2
3 4
5 2
5 4
6 5
6 4
%

Sample Output 

1 2 4 3 1
1 3 2 5 4 6 1