You will be given a series of undirected graphs. For this assignment, you must determine if for the given graph a Hamiltonian path exists.

A Hamiltonian path is a sequence of *distinct* edges that connects each
vertex exactly once.

This problem is an implementation of Algorithms Homework 1 Question 3.

The input will be a number of graphs. The first line of input for each graph will contain a single integer, representing the number of vertices. What follows will be the N x N adjacency matrix for that graph.

N A_1,1 A_1,2 ... A_1,N A_2,1 A_2,2 ... A_2,N ... ... ... ... A_N,1 A_N,2 ... A_N,N

For each graph, you should output

Graph i contains a Hamiltonian path

or

Graph i does not contain a Hamiltonian path.

Given the following input:

8 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 1 0 1 1 0 0 0 0 1 1 0 1 1 0 0 0 1 1 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0

Your program should output the following:

Graph 0 contains a Hamiltonian path.

To submit your solution, you must initiate a **Merge Request** in your
private **assignments** repository and assign it to the appropriate TA
from the Challenge 10 - TA assignment list.

To facility the **Merge Request** workflow, you must do your development in
its own [branch]:

$ cd path/to/repo # Go to your repository $ git checkout master # Make sure we are on master branch $ git pull # Make sure we have changes for GitLab $ git pull upstream master # Fetch and merge upstream changes $ git checkout -b challenge10_ec # Create challenge10_ec branch ... # Do your work $ git commit # Commit your work (can do this multiple times) $ git push -u origin challenge10_ec # Push branch to GitLab