CF258D Little Elephant and Broken Sorting

小象非常喜欢从 $1$ 到 $n$ 的整数排列，但他最喜欢的还是将它们排序。为了排序一个排列，小象需要反复交换其中的某些元素，直到最终得到排列 $1,2,3,\ldots,n$。 这一次，小象拥有一个排列 $p_{1},p_{2},\ldots,p_{n}$。他的排序程序需要恰好进行 $m$ 次操作，第 $i$ 次操作时，它会交换当前排列中第 $a_{i}$ 个和第 $b_{i}$ 个位置的元素。但是小象的排序程序坏掉了，每一步操作时，它等概率地选择什么都不做或者按照要求交换元素。 现在小象已经不抱希望能够将排列排序了，但他还是想知道：如果他运行这个程序并得到一个排列，经过所有操作后，这个排列与已经排序好的排列有多相似？请帮助小象计算：所有操作结束后，这个排列中逆序对的期望个数是多少。 我们称一对整数 $i, j\ (1 \leq i < j \leq n)$ 是排列 $p_{1},p_{2},\ldots,p_{n}$ 的一个逆序对，如果 $p_{i} > p_{j}$。

第一行包含两个整数 $n$ 和 $m$，表示排列的长度和操作的次数，其中 $1 \leq n, m \leq 1000$ 且 $n > 1$。第二行包含 $n$ 个互不相同且不超过 $n$ 的正整数，表示初始排列。接下来 $m$ 行，每行包含两个整数 $a_i$ 和 $b_i$，表示第 $i$ 次操作交换的元素位置，满足 $1 \leq a_i, b_i \leq n$ 且 $a_i \neq b_i$。

输出一行一个实数，为问题的答案。在绝对误差或相对误差不超过 $10^{-6}$ 的情况下，答案将被认为是正确的。

由 ChatGPT 5 翻译