CF258D.Little Elephant and Broken Sorting

The Little Elephant loves permutations of integers from 1 to n very much. But most of all he loves sorting them. To sort a permutation, the Little Elephant repeatedly swaps some elements. As a result, he must receive a permutation 1, 2, 3, ..., n.

This time the Little Elephant has permutation _p_1, _p_2, ..., p__n. Its sorting program needs to make exactly m moves, during the i-th move it swaps elements that are at that moment located at the a__i-th and the b__i-th positions. But the Little Elephant's sorting program happened to break down and now on every step it can equiprobably either do nothing or swap the required elements.

Now the Little Elephant doesn't even hope that the program will sort the permutation, but he still wonders: if he runs the program and gets some permutation, how much will the result of sorting resemble the sorted one? For that help the Little Elephant find the mathematical expectation of the number of permutation inversions after all moves of the program are completed.

We'll call a pair of integers i, j (1 ≤ i < j ≤ n) an inversion in permutatuon _p_1, _p_2, ..., p__n, if the following inequality holds: p__i > p__j.

小象非常喜欢整数 $1$ 到 $n$ 的排列。但其中他最爱的，是将排列进行排序。为了对一个排列进行排序，小象会反复交换某些元素，最终得到排列 $1,\,2,\,3,\,\ldots,\,n$。

这一次，小象手上有排列 $p_1,\,p_2,\,\ldots,\,p_n$。它的排序程序需要恰好执行 $m$ 步操作；在第 $i$ 步中，它本应交换当前位于第 $a_i$ 个位置和第 $b_i$ 个位置上的元素。但小象的排序程序不幸损坏了，因此在每一步中，它以相等的概率选择：要么什么也不做，要么按要求交换这两个位置上的元素。

现在小象甚至不指望该程序能成功将排列排序，但他仍好奇：若运行该程序并得到某个最终排列，那么该结果与已排序排列（即 $1,\,2,\,\ldots,\,n$）的“相似程度”如何？为此，请帮助小象计算：在程序全部 $m$ 步操作执行完毕后，所得排列中逆序对数量的数学期望值。

我们称一对整数 $i,\,j$（其中 $1 \le i < j \le n$）为排列 $p_1,\,p_2,\,\ldots,\,p_n$ 中的一个逆序对，当且仅当满足不等式：$p_i > p_j$。

The first line contains two integers n and m (1 ≤ n, m ≤ 1000, n > 1) — the permutation size and the number of moves. The second line contains n distinct integers, not exceeding n — the initial permutation. Next m lines each contain two integers: the i-th line contains integers a__i and b__i (1 ≤ a__i, b__i ≤ n, a__i ≠ b__i) — the positions of elements that were changed during the i-th move.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 1000$，且 $n > 1$）—— 分别表示排列的长度和移动次数。
第二行包含 $n$ 个互不相同的整数，均不超过 $n$ —— 表示初始排列。
接下来的 $m$ 行，每行包含两个整数：第 $i$ 行包含整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq n$，且 $a_i \neq b_i$）—— 表示第 $i$ 次移动中被交换的两个元素的位置。

In the only line print a single real number — the answer to the problem. The answer will be considered correct if its relative or absolute error does not exceed 10 - 6.

在唯一的一行中输出一个实数——该问题的答案。若答案的相对误差或绝对误差不超过 $10^{-6}$，则视为正确。