Задача №111699. Зачет
Зачет проводится в аудитории, в которой стоит один большой круглый стол, за которым ровно N мест; студентов в группе тоже ровно N. За время семестра преподаватель успел выделить несколько пар студентов, которые, по его мнению, могут списывать друг у друга, при этом каждый студент входит не более чем в одну такую пару. Теперь он хочет придумать такую рассадку для студентов, чтобы они все решали задачи самостоятельно.
Преподаватель считает, что списывать сложнее всего, если тот, у кого списывают, находится на расстоянии ровно L от того, кто списывает. Таким образом, преподаватель хочет рассадить студентов так, чтобы между каждыми двумя студентами, которые могут списывать друг у друга, сидело бы ровно L - 1 других студентов. Помогите преподавателю найти такую рассадку. Примечание. Ясно, что в зависимости от того, с какого именно из двух студентов начинать считать, и в зависимости от того, в какую сторону считать, получится разное количество человек, сидящих между ними. Преподавателю требуется лишь, чтобы для каждой пары, начиная с хотя бы какого-нибудь из этих двух студентов, хотя бы в какую-нибудь сторону до другого насчитывался бы ровно L - 1 студент.
Первая строка входного файла содержит три числа: N, L и K, где N — количество студентов в группе, L — оптимальное “антисписывательное” расстояние, а K — количество пар студентов, которые могут друг у друга списывать. Далее следуют K строк по два числа в каждой — номера студентов, входящих в очередную пару. Студенты нумеруются от 1 до N. Все числа во входном файле натуральные и не превосходят 8 000 гарантируется, что L ≤ N.
Если искомая рассадка существует, то выведите в выходной файл любой из возможных ответов, т. е. N чисел — номера студентов в порядке обходе стола против часовой стрелки, начиная с любого места. Если решения не существует, то выведите - 1.
5 3 2 1 4 2 3
1 2 5 4 3