在高桥工作的AtCoder社 ， 社员会全员坐在一张圆桌周围开会。

因为每个人都有自己喜欢的位置 ，所以以前位置是固定的 ， 但今天高桥要改变部员的座位。

高桥将会随机选择两个人并且交换他们的位置 ， 经过一定次数的交换后 ，新的位置配置就确定了。

残念的是 ，AtCoder社有一些相邻就会说话不停而影响会议的两人组。

高桥是个认真的人 ， 为了让会议不被延迟地完成 ， 他想让那些两人组一组也不要相邻。

在交换位置之后 ， 求不能相邻的两人组一组也没有相邻的概率。

输入

第一行是社员总数 $N$ 与 两人组组数 $M$ 与 交换次数 $K$

之后 $M$ 行 ， 每行一对不能相邻的两人组 $A_i$ $B_i$ $(0 <= A_i < B_i <= N)$

将社员表示为高桥向右看第几人 ， $A_i = 0$ 或 $B_i = 0$ 表示高桥自己

输出

在 $K$ 次交换后 ， 两人组全都不相邻的概率。

输出的绝对误差或相对误差在 2e-3 以下是允许的

最后 ， 输出换行符

由 @保登心爱 提供翻译