Challenge 19: Hamiltonian Cycle

Alexander Hamilton needs your help. He needs to ride around the country and rally the troops, because:

The plan is to fan this spark into a flame.

Though frustrated by the lack of resources provided by the Continental Congress, Hamilton believes:

I'm just like my country - I'm young, scrappy, and hungry, and I am not throwing away my shot.

Undeterred by the might of the British empire, he confidently proclaims:

I may not live to see our glory, but I will gladly join the fight. And when our children tell our story, they’ll tell the story of tonight.

Help Hamilton in his fight against the dreaded red coats by charting a path through a set of checkpoints such that he only visits each checkpoint once and that he returns from where he started (ie. completes a cycle).

Hurry, there is no time to waste! This is your shot! After all:

When you got skin in the game, you stay in the game. But you don’t get a win unless you play in the game. Oh, you get love for it. You get hate for it. You get nothing if you... Wait for it, wait for it, wait.

Input

The input will be a series of graphs in the following format:

N1
Ui1 Uj1
...
%
N2
Ui1 Uj1
...
%

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. Each graph is terminated with a %.

Example 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
%

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 ...

If no such path exists, then output:

None

Note: To ensure consistent output, make sure you traverse the neighbors of a vertex in sorted order.

Example Output

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

Submission

To submit your work, follow the same procedure you used for Reading 00:

$ cd path/to/cse-30872-fa18-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitLab

$ git checkout -b challenge19               # Create and checkout challenge19 branch

$ $EDITOR challenge19/program.cpp           # Edit your code

$ git add challenge19/program.cpp           # Stage your changes
$ git commit -m "challenge19: done"         # Commit your changes

$ git push -u origin challenge19            # Send changes to GitLab

To check your code, you can use the .scripts/submit.py script or curl:

$ .scripts/submit.py
Submitting challenge19 assignment ...
Submitting challenge19 code ...
  Result Success
   Score 6.00
    Time 0.03

$ curl -F source=@challenge19/program.cpp  https://dredd.h4x0r.space/code/cse-30872-fa18/challenge19
{"score": 6, "result": "Success"}

Once you have commited your work and pushed it to GitLab, member to create a merge request. Refer to the Reading 10 TA List to determine your corresponding TA for the merge request.