Problem F
Röðun
Languages
en
is
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 |
