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

#### Programming Challanges

This is based on 775 - Hamiltonian Cycle problem on the UVa Online Judge.

## Submission

``````\$ cd path/to/cse-30872-fa19-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 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-fa19/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.