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

#### Algorithmic Complexity¶

For each input test case, your solution should have the following targets:

 Time Complexity `O(V!)`, where `V` is the number of vertices in the graph. Space Complexity `O(V)`, where `V` is the number of vertices in the graph.

Your solution may be below the targets, but it should not exceed them.

#### Programming Challanges¶

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

## Submission¶

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

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

\$ 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 GitHub
``````

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

``````\$ .scripts/check.py
Checking challenge19 program.cpp ...
Result Success
Time 0.03
Score 6.00 / 6.00

\$ curl -F source=@challenge19/program.cpp https://dredd.h4x0r.space/code/cse-30872-fa22/challenge19
{"result": "Success", "score": 6, "time": 0.032061100006103516, "value": 6, "status": 0}
``````

#### Pull Request¶

Once you have committed your work and pushed it to GitHub, remember to create a pull request and assign it to the appropriate teaching assistant from the Reading 10 TA List.