C. Размещение
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

В 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 на церемонии награждения в этом году.

Входные данные

В первой строке записано три целых числа n, y и m (1 ≤ n ≤ 16, 2001 ≤ y ≤ 1018, 0 ≤ m ≤ 100) — соответственно, количество профессоров, год, для которого следует вывести порядок размещения профессоров и количество пар мест, про которые известно, что отношение старшинства профессоров должно соблюдаться.

Далее в m строках записаны m пар целых чисел «ai bi», для которых должно выполняться требование, что профессор, занимающий место ai, старше профессора, занимающего место bi (1 ≤ ai, bi ≤ n, ai ≠ bi). Некоторые пары могут быть перечислены более одного раза.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать поток cin (также вы можете использовать спецификатор %I64d).

Выходные данные

Выведите порядок размещения профессоров в году y.

Если к этому году размещения, удовлетворяющие вышеописанным требованиям, закончатся, или заданные отношения старшинства противоречивы, выведите «The times have changed» (без кавычек).

Примеры
Входные данные
3 2001 2
1 2
2 3
Выходные данные
1 2 3
Входные данные
7 2020 6
1 2
1 3
2 4
2 5
3 6
3 7
Выходные данные
1 2 3 7 4 6 5
Входные данные
10 3630801 0
Выходные данные
The times have changed
Входные данные
3 2001 3
1 2
2 3
3 1
Выходные данные
The times have changed
Примечание

В первом примере лексикографически первым является порядок «1 2 3».

В третьем примере после 3630800-го года допустимые порядки размещения закончатся.

В четвертом примере не существует ни одного размещения удовлетворяющего всем ограничениям.

Лексикографическое сравнение размещений реализует оператор < в современных языках программирования. Размещение a лексикографически меньше размещения b, если существует такое i (1 ≤ i ≤ n), что ai < bi, а для любого j (1 ≤ j < i) aj = bj.