问题文

在高橋君工作的AtCoder公司，员工们总是围坐在一张圆桌周围进行会议。
由于每个人都有自己喜欢的座位，所以座位总是相同的，但今天决定进行换座位。
高橋君被要求随机选择两个人进行位置交换，并在重复这个动作K次后得到新的座位安排。
然而，不幸的是，在AtCoder公司中存在着两个人组合，如果他们相邻坐在一起就会在会议上唠叨影响会议。
由于高橋君非常认真，他不希望任何一对这样的人组合坐在一起。
请计算在进行了座位调整之后，不允许相邻的两个人组合相邻的概率。

输入

输入以以下格式给出。N M K
A1 B1
A2 B2
...
AM BM

• 第一行是三个整数N、M和K，分别表示员工总数，不允许相邻的人组合数量，和交换的次数，两个数之间用空格分隔。
• 接下来的M行，每行包含两个整数，用空格分隔，表示不能相邻的两个人的编号。
• 第i+1行的整数Ai和整数Bi（0 ≤ Ai < Bi < N）表示不允许相邻的两个人，并且表示高橋君右边的第几个人。
• 如果Ai = 0或者Bi = 0，则表示高橋君自己。

输出

在进行了K次交换后，不允许相邻的两个人组合相邻的概率，输出到标准输出上，单独输出一行。
如果绝对误差或相对误差至少有一个小于2e-3，则认为结果是正确的。
最后输出一个换行符。

输入例子 1

4 1 1
0 3

输出例子 1

0.333333333333

• 进行座位调整之前，4个人的座位如下图所示：

• 进行一次座位调整时，为了保证0和3不相邻，
• 先调换0和1的位置。

• 再调换2和3的位置。

• 总共有2种方案符合条件，从4个人中选择2个人的方式有6种，因此满足条件的概率是2/6，答案是1/3。

输入例子 2

5 4 20
0 1
0 2
0 3
0 4

输出例子 2

0

• 除了高橋君之外的4个人中，没有人能够与高橋君相邻，所以不可能满足条件。

输入例子 3

5 1 2
0 3

输出例子 3

0.52

• 进行两次交换后，有52种方法使得0和3不相邻。
• 从5个人中选择2个人的组合方式为(5C2)^2 = 100种。
• 因此，答案是 52/100 = 0.52。

来源

ARC 003