AT_arc003_4 [ARC003D] シャッフル席替え

在高桥君工作的 AtCoder 公司，所有员工总是围坐在一张圆桌旁开会。 每个人都有自己喜欢的座位，所以平时大家的座位都是固定的，但今天决定进行一次换座。 高桥君会随机选择 $2$ 个人并交换他们的位置，这样的操作会进行指定的次数，操作结束后的座位排列就是新的座位顺序。 然而，不幸的是，在 AtCoder 公司中存在一些员工对，如果他们坐在一起就会在会议中聊天，影响会议进行。 高桥君很认真，他希望会议能顺利进行，所以不希望让任何这样的一对员工坐在一起。 请你计算在恰好进行了 $K$ 次换座操作后，没有任何一对不应相邻的员工坐在一起的概率，并将结果输出到标准输出。 输入格式如下所示。

第一行包含三个整数 $N$（员工总数，$2 \leq N \leq 11$）、$M$（不应相邻的员工对数，$0 \leq M \leq 10$）、$K$（交换次数，$0 \leq K \leq 20$），以空格分隔。 接下来的 $M$ 行，每行包含两个整数 $A_i$ 和 $B_i$（$0 \leq A_i, B_i < N$），表示一对不应相邻的员工。$A_i$ 和 $B_i$ 分别表示从高桥君起顺时针数第 $A_i$ 和第 $B_i$ 个人。 如果 $A_i = 0$ 或 $B_i = 0$，则表示高桥君本人。

输出一个实数，表示恰好进行了 $K$ 次换座操作后，没有任何一对不应相邻的员工坐在一起的概率。 如果你的答案的绝对误差或相对误差中至少有一项不超过 $2 \times 10^{-3}$，则视为正确。 最后请输出换行符。

由 ChatGPT 4.1 翻译