Irma 在图书馆工作。每天她都会看着访客从书架上拿走几本书阅读，然后把书放回原处。通常人们会弄乱顺序，并交换他们阅读的两本书。让我们看一个特定的书架，上面有 $n$ 本书，按某种顺序排列，从左到右编号为 $1$ 到 $n$。第 $i$ 位访客从位置 $x_i$ 和 $y_i$ 取走书，并把它们放回相同的位置，但顺序颠倒了。在第 $i$ 位访客之后，原本在 $x_i$ 位置的书现在位于 $y_i$ 位置，反之亦然。
傍晚图书馆关门后，Irma 想要把所有的书都放回它们各自的位置。对于每一本书，都有一个数字 $p_i$ —— 表示该书最终应该处于的位置。为了重新排列书籍，Irma 可以从书架上取出任意一本书，并将其插入到书架的最前面或最后面（这样它就会处于书架的第一个或最后一个位置）。
Irma 将所有书按顺序排列所需的最少移动次数是多少？请回答初始放置（由 $p_i$ 确定）以及在每次交换了两本书的访客之后，这一问题。
输入格式
第一行包含两个整数 $n$ 和 $q$ ($2 \le n \le 2 \cdot 10^5$; $0 \le q \le 2 \cdot 10^5$)，分别表示书架上的书的数量和访客的数量。下一行包含 $n$ 个不同的整数 $p_i$ ($1 \le p_i \le n$)，表示第 $i$ 个位置上的书最终必须处于位置 $p_i$。
接下来的 $q$ 行描述了图书馆的访客。每一行包含两个整数 $x_i, y_i$ ($1 \le x_i < y_i \le n$)，表示第 $i$ 位访客交换了位置 $x_i$ 和 $y_i$ 上的两本书。
输出格式
输出 $q+1$ 个整数 —— 分别表示初始顺序、经过第一位访客后的顺序，……，以及经过所有 $q$ 位访客后的顺序，将所有书排序所需的最少移动次数。
子任务
| 子任务 | 分值 | 数据范围 |
|---|---|---|
| 1 | 10 | $n, q \le 8$ |
| 2 | 15 | $n, q \le 200$ |
| 3 | 15 | $n \le 2000; q = 0$ |
| 4 | 15 | $n, q \le 2000$ |
| 5 | 20 | $n \le 2 \cdot 10^5; q = 0$ |
| 6 | 25 | $n, q \le 2 \cdot 10^5$ |
样例
样例输入 1
5 2 5 1 2 4 3 4 5 1 4
样例输出 1
2 1 3
说明
初始书的顺序是 $(5, 1, 2, 4, 3)$。为了整理这些书，首先将书 $4$ 移到最后，然后对书 $5$ 执行同样的操作。在第一位访客之后，书架看起来像 $(5, 1, 2, 3, 4)$；只需将书 $5$ 移到最后即可。在第二位访客之后，书的顺序是 $(3, 1, 2, 5, 4)$。对于这个顺序，最少移动次数是 $3$，有几种方法可以在 $3$ 次移动内达到最终顺序。