问题陈述
您有 $N$ 个整数的排列 $p$。最初 $p_i = i$ 成立 $1 \le i \le N$。对于每个 $j \ (1 \le j \le N)$,对于任何 $k \ge 1$,我们表示 $p^0_j = j$ 和 $p^k_j = p^{k-1}_{p_j}$。 的 期间 $p$ 的 定义为对于每个 $j \ (1 \le j \le N)$ 满足 $p^k_j = j$ 的最小正整数 $k$。
您收到 $Q$ 查询。第 $i$ 查询的特征是两个不同的索引 $x_i$ 和 $y_i$。对于每个查询,交换 $p_{x_i}$ 和 $p_{y_i}$,然后按给定顺序计算更新的 $p$ 模 $10^9 + 7$ 的周期。
可以证明$p$的周期始终存在。
输入
输入由以下格式的单个测试用例组成。
$N\Q$ $x_1\y_1$ $\vdots$ $x_Q \ y_Q$
第一行由两个整数 $N$ 和 $Q$ 组成($2 \le N \le 10^5, 1 \le Q \le 10^5$)。 第 $(i+1)$ 行由两个整数 $x_i$ 和 $y_i$ 组成($1 \le x_i, y_i \le N, x_i \ne y_i$)。
输出
在一行中打印每个查询的答案。
示例输入 1
5 4 2 5 2 4 1 3 1 2
样本输入 1 的输出
2 3 6 5
$p$ 更改如下:$[1,2,3,4,5] \to [1,5,3,4,2] \to [1,4,3,5,2] \to [3,4,1,5,2] \to [4,3,1,5,2]$。
示例输入 2
2 2 1 2 1 2
样本输入 2 的输出
2 1
$p$ 更改如下:$[1,2] \to [2,1] \to [1,2]$。
示例输入 3
10 10 5 6 5 9 8 2 1 6 8 1 7 1 2 6 8 1 7 4 8 10
样本输入 3 的输出
2 3 6 4 6 7 12 7 8 9