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。