#include <stdio.h>
#include <stdlib.h>

int readGraph(int n, int m, int graph[]){ //Parse the graph. Where n is vert, and m is edge.
	int valid = 1;
	for(int i = 0; i < (m*2) && valid == 1; i=i+2){
		valid = scanf("%d", &graph[i]);
		if(valid != 1){
			printf("Invalid data.\n");
			return 1;
		}
		valid = scanf("%d", &graph[i+1]);
		if(valid != 1){
			printf("Invalid data.\n");
			return 1;
		}
	}
	if (valid != 1){
		printf("Invalid data.\n");
		return 1;
	}else{
		return 0;
	}
}

int highestGraph(int n, int m, int graph[]){ //Check for the largest vertice in graph[]. Where n is vert, and m is edge.
	int chonk = 0;
	for(int i = 0; i < (m*2); i=i+2){
		if(graph[i] > chonk){
			chonk = graph[i];
		}else if(graph[i+1] > chonk){
			chonk = graph[i+1];
		}
	}
	return chonk;
}

int main(int argc, char * * argv){

	int verts = NULL;
	int edges = NULL;
	int chonk = NULL;
	int tf = NULL;
	int pathCur = NULL;
	int pathNex = NULL;

	int valid = scanf("%d", &verts);
	if(valid != 1){
		printf("You nincompoop, put a valid value in.");
		return EXIT_FAILURE;
	}
	valid = scanf("%d", &edges);
	int graph[verts*verts];

	if(valid != 1){
		printf("You nincompoop, put a valid value in.");
		return EXIT_FAILURE;
	}

	tf = readGraph(verts, edges, graph);
	printf("Return value of: \"%d\", The array is created.\n", tf);

	if(tf == 1){
		return EXIT_FAILURE;
	}

	chonk = highestGraph(verts, edges, graph);

	int hami[(chonk+1)*2]; //Create the array that will hold all Hamilton variables in the first section and be crossed off as they are traversed in the second section of the array.
	int checker = 0;
	for(int i = 0; i < ((chonk+1)*2); i=i+2){
		hami[i] = checker; //Set each position of the array to it's vertice number in the graph.
		hami[i+1] = 0; //Set the hami check to 0.
		checker++;
	}

	printf("Once you have input all path values, end the input stream with ctrl+d.\n");


	valid = scanf("%d", &pathCur);
	while(valid == 1){
		int cont = 0; //Continue only if this is 1,which means it has gone through the vertices and found a valid edge.
		valid = scanf("%d", &pathNex);
		for(int i = 0; i< (edges*2); i=i+2){
			if(graph[i] == pathCur && graph[i+1] == pathNex){
				for(int o = 0; o < ((chonk+1)*2); o=o+2){
					if(pathCur == hami[o]){ //If the current position equals a vertice.
						if(hami[o+1] == 0){
							hami[o+1] = -1;
						}else{
							hami[o+1] = -2;
						}
					}
				}
				cont = 1;

			}
		}
		if(cont == 0 && valid != EOF){
			printf("This is an invalid edge.\n");
			printf("This is NOT a path\nand is NOT a Hamiltonian path.\n");
			return EXIT_FAILURE;
		}
		pathCur = pathNex;
	}

	for(int i = 0; i < ((chonk+1)*2); i=i+2){
		if(pathNex == hami[i]){ //If the current position equals the final vertice.
			if(hami[i+1] == 0){
				hami[i+1] = -1;
			}else{
				hami[i+1] = -2;
			}
		}
	}

	int hamiV = 0;
	for(int i = 0; i < ((chonk+1)*2); i=i+2){
		if(hami[i+1] == -1){
			hamiV = 1;
		}else{
			hamiV = 0;
			break;
		}
	}

	printf("This is a path\n");

	if(hamiV == 1){
		printf("and is a Hamiltonian path.\n");
	}else{
		printf("and is NOT a Hamiltonian path.\n");
	}

	if(valid == 1){
		return EXIT_SUCCESS;
	}else{
		return EXIT_FAILURE;
	}
}