|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Задача 13-3. Построение
| Имя входного файла | input.txt |
| Имя выходного файла | output.txt |
| Максимальное время работы на одном тесте: | 1 секунда |
Группа солдат-новобранцев прибыла в армейскую часть N666. После знакомства с прапорщиком стало очевидно, что от работ на кухне по очистке картофеля спасти солдат может только чудо.
Прапорщик, будучи не в состоянии запомнить фамилии, пронумеровал новобранцев от 1 до N. После этого он велел им построиться по росту (начиная с самого высокого). С этой несложной задачей могут справиться даже совсем необученные новобранцы, да вот беда, прапорщик уверил себя, что знает про некоторых солдат, кто из них кого выше, и это далеко не всегда соответствует истине.
После трех дней обучения новобранцам удалось выяснить, что знает (а точнее, думает, что знает) прапорщик. Помогите им, используя эти знания, построиться так, чтобы товарищ прапорщик остался доволен.
Формат входных данных
Во входном файле cначала идут числа N и M (1 <= N <= 100,
1 <= M <= 5000) - количество солдат в роте и
количество пар солдат, про которых прапорщик знает,
кто из них выше. Далее идут эти пары чисел A и B по
одной на строке (1 <= A,B <= N), что означает,
что, по мнению прапорщика, солдат A выше, чем B.
Формат выходных данных
В первой строке выведите "Yes" (если можно
построиться так, чтобы прапорщик остался доволен) или
"No" (если нет). После ответа "Yes"
на следующей строке выведите N чисел разделенных пробелами,
- одно из возможных построений.
Пример
| input.txt | output.txt |
5 4 1 3 1 4 4 3 5 2 |
Yes 5 2 1 4 3 |