← 返回题目列表

Codeforces · 107/C

C. 安排

中文机器翻译题面 查看原题

2500年,开罗德国大学(GUC)一年一度的毕业典礼至今已顺利举办了近500年。

典礼最重要的部分与礼堂内教授们的安排有关。

传统上 GUC 有 n 名教授。每个教授都有他的资历级别。所有的资历都是不同的。让我们从 1 到 n 依次列举教授,其中 1 是最资深的教授,n 是最低资的教授。

礼堂有n个座位,每位教授一个座位。这个大厅里的某些地方是为比其他地方更资深的教授准备的。更具体地,m对座位是“高级-初级”关系,并且传统要求对于所有m对座位(ai,bi),坐在“高级”位置ai的教授应该比坐在“初级”位置bi的教授更高级。

GUC对其传统非常严格,从2001年开始就严格遵守。传统要求:

- 教授的座位每年都会变化。
- 2001年的典礼是按字典顺序在礼堂中首次安排教授。
- 每年按字典顺序使用教授的下一个排列。

教授的排列是n个整数的列表,其中第一个整数是坐在第一位置的教授的资历,第二个整数是坐在第二位置的教授的资历,依此类推。

给定n,教授数量,y,当前年份和m对限制,输出今年教授的安排。

输入

第一行包含三个整数n、y和m(1≤n≤16、2001≤y≤1018、0≤m≤100)——分别为教授人数、应计算排列的年份以及应保持资历关系的席位对的数量。

接下来的m行每行包含一对整数“ai bi”,表示第ai个座位上的教授比第bi个座位上的教授资历更高(1≤ai,bi≤n,ai≠bi)。某些货币对可能会被多次列出。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin 流(您也可以使用 %I64d 指定符)。

输出

打印教授在请求年份的就座顺序。

如果到今年 GUC 已经没有安排,或者给定的“高级 - 初级”关系是矛盾的,请打印“时代已经改变”(不带引号)。

示例

输入 #1

3 2001 2
1 2
2 3

输出 #1

1 2 3

输入 #2

7 2020 6
1 2
1 3
2 4
2 5
3 6
3 7

输出 #2

1 2 3 7 4 6 5

输入 #3

10 3630801 0

输出 #3

The times have changed

输入#4

3 2001 3
1 2
2 3
3 1

输出#4

The times have changed

注意

在第一个示例中,按字典顺序排列的第一顺序是 1 2 3。

在第三个示例中,GUC 将在 3630800 年之后用完所有安排。

在第四个示例中,没有有效的座位安排。

排列的字典顺序比较是由现代编程语言中的 < 运算符执行的。如果存在这样的 i (1 ≤ i ≤ n),且 ai < bi,并且对于任何 j (1 ≤ j < i) aj = bj,则排列 a 按字典顺序小于排列 b。