CF107C Arrangement

在公元 2500 年，开罗德国大学（GUC）的年度毕业典礼已经顺利举办了近 500 年。 典礼中最重要的部分是教授们在典礼大厅中的排列。 按照传统，GUC 有 $n$ 位教授。每位教授都有其资历等级，且所有资历等级互不相同。我们将教授编号为 $1$ 到 $n$，其中 $1$ 号教授资历最高，$n$ 号教授资历最低。 典礼大厅有 $n$ 个座位，每位教授一个座位。大厅中的某些座位对更资深的教授来说更为重要。更具体地说，有 $m$ 对座位存在“资深-资浅”关系，传统要求对于所有 $m$ 对座位 $(a_i, b_i)$，坐在“资深”位置 $a_i$ 的教授必须比坐在“资浅”位置 $b_i$ 的教授更资深。 GUC 对其传统极为严格，自 2001 年起一直严格遵守。传统要求： - 教授的座次每年都要更换。 - 2001 年典礼采用的是教授在典礼大厅中的字典序第一个排列。 - 每一年都采用字典序下一个排列。 教授的排列是 $n$ 个整数的列表，第一个整数表示坐在第 1 号位置的教授的资历，第二个整数表示坐在第 2 号位置的教授的资历，依此类推。 给定 $n$（教授人数）、$y$（当前年份）和 $m$ 对限制条件，请输出该年份教授的座次排列。

第一行包含三个整数 $n$、$y$ 和 $m$（$1 \leq n \leq 16, 2001 \leq y \leq 10^{18}, 0 \leq m \leq 100$），分别表示教授人数、需要计算座次排列的年份和需要保持资历关系的座位对数。 接下来的 $m$ 行，每行包含一对整数 "$a_i$ $b_i$"，表示第 $a_i$ 个座位上的教授必须比第 $b_i$ 个座位上的教授更资深（$1 \leq a_i, b_i \leq n, a_i \neq b_i$）。同一对可能出现多次。 请不要在 C++ 中使用 %lld 读取或输出 64 位整数，建议使用 cin 流（也可以使用 %I64d）。

输出该年份教授的座次排列。 如果到该年份时 GUC 已经没有可用的排列，或者给定的“资深-资浅”关系存在矛盾，则输出“The times have changed”。

在第一个样例中，字典序第一个排列为 1 2 3。 在第三个样例中，GUC 在第 3630800 年后将没有可用的排列。 在第四个样例中，没有合法的座次排列。 排列的字典序比较方式与现代编程语言中的 < 运算符一致。排列 $a$ 在字典序上小于排列 $b$，当且仅当存在某个 $i$（$1 \leq i \leq n$），使得 $a_i < b_i$，并且对于所有 $j$（$1 \leq j < i$）都有 $a_j = b_j$。 由 ChatGPT 4.1 翻译