| Coder-Strike 2014 - Раунд 1 |
|---|
| Закончено |
Сотрудники компании R1 частенько проводят время вместе: смотрят футбол, отдыхают на природе, решают контесты. Поэтому нет ничего особенного в том, что иногда кто-то платит за кого-то.
Сегодня день выдачи премий. Глава компании R1 будет приглашать сотрудников в свой кабинет по одному, награждая каждого за усердную работу в этом месяце. Глава компании хорошо знает, кто кому должен. А также он понимает, что если пригласить человека x в кабинет за премией, а затем сразу же пригласить человека y, которому человек x должен, то они могут встретиться. Конечно, в такой ситуации радость человека x от только что полученной премии будет намного меньше. Поэтому глава R1 решил приглашать сотрудников в таком порядке, что описанная ситуация не будет происходить ни для какой пары сотрудников, приглашенных один за другим.
Однако сотрудников в компании много, а времени у главы компании — нет. Поэтому задачу поручили вам. По заданным отношениям долга между всеми сотрудниками определите, в каком порядке следует приглашать их в кабинет главы R1, либо определите, что описанного порядка не существует.
В первой строке записаны через пробел целые числа n и m 
— количество сотрудников в R1 и количество отношений долга. В каждой из следующих m строк записано два целых числа через пробел ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi), эти числа обозначают, что человек с номером ai должен человеку с номером bi. Считайте, что все сотрудники пронумерованы от 1 до n.
Гарантируется, что каждая пара людей p, q упоминается во входных данных не более одного раза. В частности, входные данные не будут содержать пар p, q и q, p одновременно.
Выведите -1, если описанного порядка не существует. Иначе, выведите перестановку из n различных целых чисел. Первое число должно обозначать номер человека, которого надо позвать первым в кабинет главы R1, второе — номер второго человека, и так далее.
Если существует несколько правильных порядков, разрешается вывести любой.
2 1
1 2
2 1
3 3
1 2
2 3
3 1
2 1 3
