#P3949. 买置换
买置换
题目描述
买菜否开了一家店,号称「一切皆可买」,生意红火。
这天 crx 看到店里面有一个很长的置换 ,它的形式非常优美。若将其表示成排列 ,则对所有 都有
买菜否表示,只要 crx 能求出 的特征值,就让 crx 低价买下这个置换。
对任意一个置换 ,定义它的特征值为: 能生成的所有不同置换的循环数之和。其中,“能生成”是指 的一个或多个幂(反复与自身复合),循环数是将置换分解成互不相交的循环后,循环的个数。只需输出特征值模 的结果。
买菜否依次进行了 次操作。每次给定两个不同的整数 ,把排列中数值为 和数值为 的两个元素交换(不是交换下标为 的两个位置)。求每次操作完成后当前置换的特征值。
输入格式
第一行两个整数 ,表示置换长度和操作次数。
接下来 行,每行两个整数 ,表示交换当前排列中数值为 、 的两个数。
输出格式
输出 行,第 行一个整数,为第 次操作后置换的特征值对 取模的结果。
样例输入
4 2
4 3
1 3
样例输出
8
8
样例说明
第一次交换后,置换为 。它产生三个不同置换,循环数依次为 ,因此答案为 。
第二次交换后,置换为 ,是一个长度为 的单循环,其特征值为 。
数据范围
- 。
- 。
- 且 。
特别说明:由于 且 ,不存在满足所有输入限制的 测试数据。正式数据均取 。