Hide

Problem H
Röðun

One of the popular tasks in computer science is the problem of sorting. Given a list of sortable items, for example numbers or strings, with the goal being to order them in either increasing or decreasing order. In this problem the task is to sort a list of contestants’ names in increasing order by number of problems solved. Pairs of names will be given, saying which of the contestants solved more problems. No two contestants solved the same number of problems. Find the order of the contestants or say that there isn’t enough information to figure it out.

Input

The first line of the input contains integers $n$ and $k$, where $n$ is the number of contestants and $k$ is the number of comparisons made. Then there is a line with $n$ names, each given with only a single name and no two contestants having the same name. Then there are $k$ lines containing the comparisons, i.e. a line with the names of two contestants separated by either $<$ or $>$, giving which one of them solved more problems. Ed $>$ Bob means Ed solved more problems than Bob but Jim $<$ Cox means Jim solved fewer problems than Cox. The same two contestants are not compared more than once. The name of each contestant is at most $8$ characters.

Output

The names of the contestants in increasing order by their number of solved problems, separated by spaces, if the order can be deduced. If there is not enough information given, instead print veit ekki.

Scoring

Group

Points

Constraints

1

20

$0 < n \leq 400$, $k = \frac{n \cdot (n-1)}{2}$, all comparisons given

2

30

$0 < n \leq 100$, $0 \leq k < \frac{n \cdot (n-1)}{2}$

3

50

$100 < n \leq 100000$, $0 \leq k < \min \left(100001, \frac{n \cdot (n-1)}{2}\right)$

Sample Input 1 Sample Output 1
3 3
Arnar Benni Unnar
Arnar > Benni
Benni < Unnar
Unnar < Arnar
Benni Unnar Arnar
Sample Input 2 Sample Output 2
6 5
Andrea Arna Freyja Hanna Sigga Unnur
Freyja > Sigga
Hanna < Sigga
Arna > Unnur
Andrea > Arna
Andrea < Hanna
Unnur Arna Andrea Hanna Sigga Freyja
Sample Input 3 Sample Output 3
8 12
Bernhard Ernhardb Rnhardbe Nhardber Hardbern Ardbernh Rdbernha Dbernhar
Bernhard > Ernhardb
Ernhardb > Rnhardbe
Rnhardbe > Nhardber
Rnhardbe > Hardbern
Rnhardbe > Ardbernh
Rnhardbe > Rdbernha
Rnhardbe > Dbernhar
Nhardber > Ardbernh
Hardbern > Ardbernh
Ardbernh > Rdbernha
Ardbernh > Dbernhar
Dbernhar < Rdbernha
veit ekki
CPU Time limit 1 second
Memory limit 1024 MB
Languages English, Íslenska
Authors
Arnar Bjarni Arnarson and Sigurður Jens Albertsson
Source Forritunarkeppni Framhaldsskólanna 2018
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in