小象非常喜欢1到n的整数排列。但最重要的是,他喜欢对它们进行分类。为了对排列进行排序,小象会反复交换一些元素。结果,他必须得到排列 1, 2, 3, ..., n。
这次小象有排列 p1, p2, ..., pn。它的排序程序需要恰好进行 m 次移动,在第 i 次移动期间,它交换当时位于第 ai 和第 bi 个位置的元素。但是小象的排序程序碰巧崩溃了,现在每一步它都可能要么什么都不做,要么交换所需的元素。
现在小象甚至不希望程序对排列进行排序,但他仍然想知道:如果他运行程序并得到一些排列,排序的结果与排序后的结果有多少相似?为此,请帮助小象找到程序所有移动完成后排列反转次数的数学期望。
如果以下不等式成立,我们将一对整数 i, j (1 ≤ i < j ≤ n) 称为排列 p1, p2, ..., pn 的反转:pi > pj。
输入
第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 1000, n > 1) — 排列大小和移动次数。第二行包含 n 个不同的整数,不超过 n - 初始排列。接下来的 m 行每行包含两个整数:第 i 行包含整数 ai 和 bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — 第 i 次移动期间更改的元素的位置。
输出
在唯一的一行中打印一个实数——问题的答案。如果答案的相对误差或绝对误差不超过 10 - 6,则认为答案是正确的。
示例
输入 #1
2 1 1 2 1 2
输出 #1
0.500000000
输入 #2
4 3 1 3 2 4 1 2 2 3 1 4
输出 #2
3.000000000