training_2004_12_04 - Topological sorting

Problem B. Topological sorting ≡

problems
visible spaces
basic formulae
wide text
editor

Author:	StdAlg	Time limit:	1 sec
Input file:	input.txt	Memory limit:	8 Mb
Output file:	output.txt

Statement

You are to write a program that performs a topological sorting of a directed graph. Graph contains N vertices, numbered with integers from 1 to N, and M edges.

In other words, given a partial order on numbers from 1 to N, your program must produce some linear order on these numbers which does not conflict with the given partial order.

Input file format

Input file contains two integers N and M, followed by M pairs of integers. Integers in each pair are different, and represent starting and ending vertex of a graph edge.

These pairs may also be considered comparisons where the first number precedes the second one.

Output file format

Output file must contain a permutation of integers from 1 to N — numbers of vertices sorted in topological order. (That is, representing a linear order.) If ordering is not possible, output file must contain a single number  − 1.

Constraints

0 ≤ N, M ≤ 100000

Sample tests

No.	Input file (`input.txt`)	Output file (`output.txt`)
1	`4 3 1 2 1 3 3 4`	`1 3 2 4`