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

typedef struct my_struct
{
	int number_of_neighbors;
	int *neighbors;

}Adjacency_List;

typedef struct linked
{
	int node;
	struct linked *next;

}LinkedList;


void DFS(Adjacency_List *adjlist, int node, bool **visited, LinkedList **head)
{
	(*visited)[node] = true;
	
	for (int i = 0; i < adjlist[node].number_of_neighbors; i++)
		if ((*visited)[adjlist[node].neighbors[i]] == false)
			DFS(adjlist, adjlist[node].neighbors[i], visited, head);

	if (*head == NULL)
	{
		*head = calloc(1, sizeof(LinkedList));
		(*head)->node = node;
		
	}
	else
	{
		LinkedList *new_node = calloc(1, sizeof(LinkedList));
		new_node->node = node;
		new_node->next = *head;
		*head = new_node;
	}

}


int main(int argc, char const *argv[])
{
	FILE *read = fopen("sortaret.in", "r");
	FILE *write = fopen("sortaret.out", "w");

	int number_of_vertices;
	int number_of_arcs;

	fscanf(read, "%d %d", &number_of_vertices, &number_of_arcs);

	bool *visited = calloc(number_of_vertices + 1, sizeof(bool));

	Adjacency_List* adjlist = calloc(number_of_vertices + 1, sizeof(Adjacency_List));

	int node1, node2;

	for(int i = 0; i < number_of_arcs; i++)
	{
		fscanf(read,"%d %d",&node1,&node2);
		
		if(adjlist[node1].number_of_neighbors == 0)
		{
			adjlist[node1].neighbors = calloc(1, sizeof(int));
		
			adjlist[node1].neighbors[0] = node2;

			adjlist[node1].number_of_neighbors = 1;
	
		}
		else
		{
			adjlist[node1].number_of_neighbors++;
		
			adjlist[node1].neighbors = realloc(adjlist[node1].neighbors, adjlist[node1].number_of_neighbors * sizeof(int));

			adjlist[node1].neighbors[adjlist[node1].number_of_neighbors - 1] = node2;
		
		}
		
		if(adjlist[node2].number_of_neighbors == 0)
		{
			adjlist[node2].neighbors = calloc(1, sizeof(int));
	
			adjlist[node2].neighbors[0] = node1;
		
			adjlist[node2].number_of_neighbors = 1;
	
		}
		else
		{
			adjlist[node2].number_of_neighbors++;
		
			adjlist[node2].neighbors = realloc(adjlist[node2].neighbors, adjlist[node2].number_of_neighbors * sizeof(int));
		
			adjlist[node2].neighbors[adjlist[node2].number_of_neighbors - 1] = node1;
		
		}

		
	}

	LinkedList *head = NULL;

	DFS(adjlist, 1, &visited, &head);

	while (head != NULL)
	{
		if (head->next == NULL)
			fprintf(write, "%d\n", head->node);
		else
			fprintf(write, "%d ", head->node);

		head = head->next;
	}
	
	for (int i = 1; i <= number_of_vertices; i++)
		if (adjlist[i].number_of_neighbors != 0)
			free(adjlist[i].neighbors);			

	free(visited);
	free(adjlist);	

	fclose(read);
	fclose(write);

	return 0;
}