#define _DEFAULT_SOURCE
#define _POSIX_C_SOURCE 200809L

#include <sys/queue.h>

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

struct node
{
	LIST_ENTRY(node) List;
	char         *Name;
	size_t        FromCount;
	size_t        ToCount;
	struct node **From;
	struct node **To;
};

enum state
{
	state_not_ready,
	state_ready,
	state_done,
};

LIST_HEAD(node_list, node);

static struct node_list Nodes;
static struct node_list NodesReady;
static struct node_list NodesDone;

static bool
Depends(struct node *A, struct node *B)
{
	for(size_t i = 0; i < A->FromCount; ++i)
		if(B == A->From[i]) return true;
	return false;
}

static struct node *
New(char *Name)
{
	struct node *N = calloc(1, sizeof(struct node));
	N->Name        = Name;
	LIST_INSERT_HEAD(&NodesReady, N, List);
	return N;
}

static void
Free(struct node *Node)
{
	free(Node->Name);
	if(Node->From != NULL) free(Node->From);
	if(Node->To != NULL) free(Node->To);
	LIST_REMOVE(Node, List);
	free(Node);
}

static struct node *
Find(struct node_list *L, char *A)
{
	for(struct node *I = L->lh_first; I != NULL; I = I->List.le_next)
	{
		if(strcmp(I->Name, A) == 0)
		{
			free(A);
			return I;
		}
	}
	return NULL;
}

static struct node *
FindWithState(char *Name, enum state *State)
{
	struct node *Node;
	*State = state_done;
	Node   = Find(&NodesDone, Name);
	if(Node != NULL) return Node;
	*State = state_ready;
	Node   = Find(&NodesReady, Name);
	if(Node != NULL) return Node;
	*State = state_not_ready;
	Node   = Find(&Nodes, Name);
	if(Node != NULL) return Node;
	*State = state_ready;
	return New(Name);
}

static void
DependencyRemove(struct node *A, struct node *B)
{
	size_t i;
	for(i = 0; i < B->ToCount; ++i)
		if(B->To[i] == A) break;
	memmove(B->To + i, B->To + i + 1, (B->ToCount - i - 1) * sizeof(struct node *));
	if(--B->ToCount == 0)
	{
		free(B->To);
		B->To = NULL;
	}
	for(i = 0; i < A->FromCount; ++i)
		if(A->From[i] == B) break;
	memmove(A->From + i, A->From + i + 1, (A->FromCount - i - 1) * sizeof(struct node *));
	if(--A->FromCount == 0)
	{
		free(A->From);
		A->From = NULL;
		LIST_REMOVE(A, List);
		LIST_INSERT_HEAD(&NodesReady, A, List);
	}
}

static void
Complete(char *Name)
{
	enum state   State;
	struct node *Node = FindWithState(Name, &State);
	switch(State)
	{
		case state_not_ready:
		case state_ready:
		{
			// TODO: Cleanup from the end should be faster because we would have half as many memmoves
			while(Node->FromCount > 0) DependencyRemove(Node, Node->From[0]);
			while(Node->ToCount > 0) DependencyRemove(Node->To[0], Node);
			LIST_REMOVE(Node, List);
			LIST_INSERT_HEAD(&NodesDone, Node, List);
			break;
		}
		case state_done: break;
	}
}

static void
DependencyAdd(char *NameA, char *NameB)
{
	enum state   StateA;
	enum state   StateB;
	struct node *A = FindWithState(NameA, &StateA);
	struct node *B = FindWithState(NameB, &StateB);
	switch(StateB)
	{
		case state_not_ready:
		case state_ready:
		{
			switch(StateA)
			{
				case state_ready:
				{
					LIST_REMOVE(A, List);
					LIST_INSERT_HEAD(&Nodes, A, List);
					goto common;
				}
				case state_not_ready:
				{
					if(Depends(A, B)) return;
					goto common;
				}
				common:
				{
					A->From = (struct node **)reallocarray(A->From, A->FromCount + 1, sizeof(struct node *));
					A->From[A->FromCount++] = B;
					B->To = (struct node **)reallocarray(B->To, B->ToCount + 1, sizeof(struct node *));
					B->To[B->ToCount++] = A;
					break;
				}
				case state_done: break;
			}
			break;
		}
		case state_done: break;
	}
}

int
main(void)
{
	LIST_INIT(&Nodes);
	LIST_INIT(&NodesReady);
	LIST_INIT(&NodesDone);
	char  *Line = NULL;
	size_t Size = 0;
	while(true)
	{
		ssize_t Count = getline(&Line, &Size, stdin);
		if(Count <= 0) break;
		if(Count > 0 && Line[Count - 1] == '\n') --Count;
		if(Count == 0)
		{
			for(struct node *At = NodesReady.lh_first; At != NULL; At = At->List.le_next)
				printf("%s ", At->Name);
			printf("\n");
			continue;
		}
		ssize_t Space   = -1;
		bool    Invalid = false;
		for(ssize_t i = 0; i < Count; ++i)
		{
			if(Line[i] == ' ')
			{
				if(Space != -1)
				{
					Invalid = true;
					break;
				}
				Space = i;
			}
		}
		if(Invalid)
		{
			fprintf(stderr, "failed to parse '%.*s'\n", (int)Count, Line);
			continue;
		}
		if(Space == -1)
		{
			Complete(strndup(Line, (size_t)Count));
		} else
		{
			char *A = strndup(Line, (size_t)Space);
			char *B = strndup(Line + Space + 1, (size_t)(Count - (Space + 1)));
			DependencyAdd(A, B);
		}
	}
	if(Line != NULL)
	{
		free(Line);
		Line = NULL;
		Size = 0;
	}
	struct node *Next;
	for(struct node *At = Nodes.lh_first; At != NULL; At = Next)
	{
		Next = At->List.le_next;
		Free(At);
	}
	for(struct node *At = NodesReady.lh_first; At != NULL; At = Next)
	{
		Next = At->List.le_next;
		Free(At);
	}
	for(struct node *At = NodesDone.lh_first; At != NULL; At = Next)
	{
		Next = At->List.le_next;
		Free(At);
	}
	return 0;
}