T690036 C-sort

小 C 发明了一种新的排序方式 C-sort，对于一个排列 $p$，该排序会重复若干轮次，每个轮次具体的过程如下： - 设 $U=\{1,2,\dots,n\}$，选择 $S\sub U$，并将所有下标在 $S$ 中的元素提到排列开头，但不改变这些元素之间的相对顺序。 例如，对于排列 $1,3,2,4$，选择 $S=\{2,4\}$，$p_2$ 和 $p_4$ 会被提到开头，此时的排列为 $3,4,1,2$。 现在给你一个排列 $p$，小 C 希望你进行 $q$ 次操作，每次操作给定两个位置 $i, j$，请你交换 $p_i$ 和 $p_j$。在交换后，输出如果要将现在的排列还原回 $1, 2, \cdots, n$，C-sort 排序最少需要进行几轮。

第一行两个整数 $n, q$。 第二行有一个长度为 $n$ 的排列，表示初始排列 $p$。 接下来 $q$ 行，每行两个整数 $i, j$。

输出一共有 $q$ 行，每次输出一行一个整数，表示将修改后的排列还原为 $1, 2, \cdots, n$ 所需要的最少轮次。

| 测试点编号 | 特殊性质 | | :--------: | :-----------: | | $1\sim2$ | $q=1$ | | $3\sim5$ | $n,q\le100$ | | $6\sim 10$ | $n, q\le1000$ | | $11\sim20$ | 无 | 对于所有数据，$1\le n,q\leq 10^6$，$p$ 是排列。