← 返回题目列表

AtCoder · jag2017summer_day3_k

K. 排列周期

中文机器翻译题面 查看原题

问题陈述

您有 $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