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