/*
	Sortarea topologica.
	Elementele unei multimi M sunt notate cu litere mici din alfabet. Se citesc perechi de
elemente x, y (x, y apartin multimii M) cu semnificatia ca elementul x precede elementul y.
Sa se afiseze elementele multimii M intr-o anumita ordine, incat pentru orice elemente x, y
cu proprietatea ca x precede pe y, elementul x sa fie afisat inaintea lui y.
*/


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

struct nod
{
	int caracter;
	int nr_predecesori;
	struct nod_l *succesori;
	nod *next;
};

struct nod_l
{
	nod *succesor;
	nod_l *next;
};

nod *root = 0 , *last = 0;


void incarca(FILE *f);
void push_lista(nod *&p,nod *p1);
void pop_lista(nod *&p);
void citeste_char(char c, char d);
nod *construieste_nod(char caracter);
void afisare();
bool verificare();

int main()
{
	FILE *f;
	f = fopen("sortaret.in","r");
	if ( f == 0 )
		return;
	incarca(f);
	afisare();


	fclose(f);
	//system("PAUSE");
	return 1;
}

void afisare()
{
	FILE *g = fopen("sortaret.out","w");
	nod *p = root;
	nod *z,*z1,*v1;
	nod_l *k1,*e1,*e2;
	if ( p == 0 )
		return;

	while ( p != 0 )
	{
		z = p;
		if ( verificare() == false )
			{
				printf("\nNu are solutie");
				z = 0;
				break;
			}
		while ( z != 0 )
		{
			if ( z->nr_predecesori == 0 )
			{
				fprintf(g,"%d ",z->caracter);
				k1 = z->succesori;
				while ( k1 != 0 )
				{
					k1->succesor->nr_predecesori--;	
					k1 = k1->next;
				}
				z1 = z;
				z = z->next;
				if ( root == z1 )
					root = root->next;
				else
				{
					v1 = root;
					while ( v1->next != z1 )
						v1 = v1->next;
					v1->next = z1->next;
				}
				e1 = z1->succesori;
				while ( e1 != 0 )
				{
					e2 = e1;
					e1 = e1->next;
					free(e2);
				}
				free(z1);


			}
			else
				z = z->next;
		}
	
		p = root;
	}
	fclose(g);
}

bool verificare()
{
	bool v = false;

	nod *p = root;
	while ( p != 0 )
	{
		if ( p->nr_predecesori == 0 )
			v = true;
		p = p->next;
	}

	return v;
}

void incarca(FILE *f)
{
	int c,d;
	int n,m;
	fscanf(f,"%d %d",&n,&m);
	for(int i=0;i<m;i++)
	{
		fscanf(f,"%d %d",&c,&d);
		citeste_char(c,d);
	}
	//do
	//{
	//	fscanf(f,"%c %c\n",&c,&d);
	//	citeste_char(c,d);
	//}
	//while (!feof(f));

}

void citeste_char(char c, char d)
{
	nod *p = root;
	nod *l,*l1=0;
	l = construieste_nod(c);
	nod *k = root;
	bool ver = false;

	while ( k != 0 )
	{
		if ( k->caracter == d )
		{
			ver = true;
			l1 = k;
		}
		k = k->next;
	}
	if ( l1 == 0 )
		l1 = construieste_nod(d);

	if ( root == 0 )
	{
		root = l;
		root->next = l1;
		push_lista(root,l1);
		last = l1;
		return;
	}

	while ( p != 0 )
	{
		if ( p->caracter == c )
		{
			push_lista(p,l1);
			free(l);
			if ( ver != true )
			{
				last->next = l1;
				last = last->next;
			}
			return;
		}
	
		p = p->next;
	}

	last->next = l;
	last = last->next;
	push_lista(l,l1);

	if ( ver != true )
		{
			last->next = l1;
			last = last->next;
		}


}

nod *construieste_nod(char caracter)
{
	nod *l = (nod *)malloc(sizeof(nod));
	l->caracter = caracter;
	l->next = 0;
	l->nr_predecesori = 0;
	l->succesori = 0;

	return l;
}

void pop_lista(nod *&p)
{
	if ( p->succesori == 0 )
		return;
	nod_l *z;
	z = p->succesori;
	p->succesori = p->succesori->next;
	free(z);
}

void push_lista(nod *&p,nod *p1)
{
	nod_l *rootl = p->succesori;
	nod_l *k;

	k = (nod_l*)malloc(sizeof(nod_l));
	k->next = 0;
	k->succesor = p1;

	if ( rootl == 0 )
	{
		p->succesori = k;
		p->succesori->succesor->nr_predecesori++;
		return;
	}

	k->next = rootl;
	p->succesori = k;
	p->succesori->succesor->nr_predecesori++;

}