В 2500-ом году ежегодная церемония вручения дипломов в German University in Cairo (GUC) приближается к своему 500-летнему юбилею.
Важной частью церемонии является размещение профессоров в зале, где происходит вручение дипломов.
В GUC есть n профессоров. У каждого профессора свой уровень старшинства, и все уровни старшинства разные. Для простоты обозначим профессоров номерами от 1 до n, где 1 соответствует самому старшему, а n — самому младшему профессору.
В зале, где проходит вручение дипломов, имеется n мест, по одному месту для каждого профессора. Некоторые места в этом зале предназначены для более старших профессоров. Конкретно, про m пар мест известно, что для пары мест (ai, bi) профессор, занимающий место ai должен быть старше профессора, занимающего место bi.
Начиная с 2001 года в GUC ответственно подходят к соблюдению традиции размещения профессоров. Традиция гласит, что:
- Порядок размещения меняется каждый год.
- В 2001 году было использовано лексикографически первое размещение.
- Каждый последующий год используется лексикографически следующее размещение.
Под размещением профессоров понимается список из n чисел, где первое число соответствует уровню старшинства профессора, занимающего место номер один, второе число соответствует уровню старшинства профессора, занимающего место номер два и так далее.
Зная n, количество профессоров в GUC, текущий год y, и m пар ограничений на размещение, выведите порядок, в котором будет размещены профессора GUC на церемонии награждения в этом году.
Выходные данные
Выведите порядок размещения профессоров в году y.
Если к этому году размещения, удовлетворяющие вышеописанным требованиям, закончатся, или заданные отношения старшинства противоречивы, выведите «The times have changed» (без кавычек).
Примечание
В первом примере лексикографически первым является порядок «1 2 3».
В третьем примере после 3630800-го года допустимые порядки размещения закончатся.
В четвертом примере не существует ни одного размещения удовлетворяющего всем ограничениям.
Лексикографическое сравнение размещений реализует оператор < в современных языках программирования. Размещение a лексикографически меньше размещения b, если существует такое i (1 ≤ i ≤ n), что ai < bi, а для любого j (1 ≤ j < i) aj = bj.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2001 2
1 2
2 3
|
1 2 3
|
|
2
|
7 2020 6
1 2
1 3
2 4
2 5
3 6
3 7
|
1 2 3 7 4 6 5
|
|
3
|
10 3630801 0
|
The times have changed
|
|
4
|
3 2001 3
1 2
2 3
3 1
|
The times have changed
|