1. 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11
* Problem: 775 Hamiltonian Cycle
* Link:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=9&page=show_problem&problem=716
*
* @author Rolf Schirm
* @version 1.0, 05/11/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.784
*/
public class Main {

private static int nodes;
private static boolean[][] containsEdge;

private static int[] path;

public static void main(String... args) throws Exception {
final BufferedReader scan = new BufferedReader(new
InputStreamReader(System.in));

String line;
while((line = scan.readLine()) != null) {
if(!line.isEmpty()) {
nodes = Integer.parseInt(line);
containsEdge = new boolean[nodes][nodes];

// Read edges
while((line = scan.readLine()) != null && !line.equals("%")) {
if(!line.isEmpty()) {
String[] split = line.split(" ");
final int num1 = Integer.parseInt(split[0]) - 1;
final int num2 = Integer.parseInt(split[1]) - 1;

// Undirected
containsEdge[num1][num2] = true;
containsEdge[num2][num1] = true;
}
}

path = new int[nodes];

// Initialize path
for(int i = 0; i < nodes; i++) {
path[i] = i;
}

boolean hasNext = true;

while(hasNext) {
// Test if the path is has a cycle
if(hasCycle()) {
// Print the solution
for(int i = 0; i < nodes; i++) {
System.out.print((path[i] + 1) + " ");
}
System.out.println((path[0] + 1));
hasNext = false;
} else {
// Get the next path
hasNext = nextPath();

// No more paths exists
if(!hasNext) {
System.out.println("N");
}
}
}
}
}
}

/**
* Test if all edges from the path exists.
*
* @return true, if a the path has a cycle
*/
private static boolean hasCycle() {
final int lastIndex = nodes - 1;
for(int i = 0; i < lastIndex; i++) {
if(!containsEdge[path[i]][path[i+1]]) {
return false;
}
}

// Close the cycle from end to start
return containsEdge[path[lastIndex]][path[0]];
}

/**
* Increment the path to the next possibility.
* The first number is static.
*
* Example with 4 nodes:
* 0123 -> 0132 -> 0213 -> 0231 -> 0312 -> 0321 -> FALSE
*
* @return true, if a next path exists
*/
private static boolean nextPath() {
boolean found = false;
for(int i = nodes - 1; i > 0 && !found; i--) {
int oldNumber = path[i];
int newNumber = nodes;
int index = -1;

for(int j = i + 1; j < nodes; j++) {
int number = path[j];
if(number < newNumber && number > oldNumber) {
newNumber = number;
index = j;
}
}

if(index >= 0) {
path[i] = newNumber;
path[index] = oldNumber;
Arrays.sort(path, i+1, nodes);
found = true;
}
}
return found;
}
}