题目描述

一位有抱负的音乐家 K 非常喜欢吃涮涮锅！最近，她按照以下算法光顾了编号为 $1, 2, \ldots, N$ 的 $N$ 家涮涮锅餐厅：

1. K 维护一个有序的推荐列表，初始时仅包含餐厅 1。
2. 在第 $i$ 天，她访问列表中下一个被推荐的餐厅，该餐厅会向她推荐餐厅集合 $R_i = \{r_{i,1}, \ldots, r_{i,l_i}\}$。
3. K 将 $R_i$ 追加到她的待访问餐厅列表中。
4. K 重复步骤 2-4，直到没有更多推荐餐厅为止。
5. K 记录数组 $A_0, \ldots, A_{N-1}$，其中 $A_i$ 表示第 $(i+1)$ 天她被推荐的餐厅数量，即 $A_i = |R_{i+1}|$。

题目保证 $\bigcup_{i=1}^{N} R_i = \{2, \ldots, N\}$ 且 $R_i \cap R_j = \emptyset$（$i \neq j$），即除了第一家餐厅外，每家餐厅恰好被另一家餐厅推荐一次。

当 K 完成列表后，她的捣蛋朋友 H 决定捉弄她！H 将数组 $A_0, \ldots, A_{N-1}$ 替换为另一个数组 $B_0, \ldots, B_{N-1}$！K 认为这个新数组 $B_i$ 可能是她的数组的循环移位，因此她请你找出所有可能的 $0 \leq k < N$，使得对于所有 $0 \leq i < N$ 和任意合法的算法输出 $A_0, \ldots, A_{N-1}$，满足 $A_i = B_{(i+k) \bmod N}$。

此外，K 还会执行 $Q$ 次操作，其中第 $i$ 次操作会交换 $B_{x_i}$ 和 $B_{y_i}$，并要求你对新数组执行相同的计算。你能帮 K 识破朋友的恶作剧吗？

输入格式

第一行输入包含两个整数 $N$（$1 \leq N \leq 500\,000$）和 $Q$（$0 \leq Q \leq 300\,000$）。

第二行输入包含 $N$ 个以空格分隔的非负整数 $B_0, B_1, \ldots, B_{N-1}$（$0 \leq B_i < N$），表示初始序列。

接下来的 $Q$ 行每行包含两个整数 $x_i$ 和 $y_i$（$0 \leq x_i, y_i < N$ 且 $x_i \neq y_i$），表示交换 $B_{x_i}$ 和 $B_{y_i}$。

输出格式

对于每个 $Q + 1$ 个数组（包括初始数组 $B_0, \ldots, B_{N-1}$），设 $S = \{k_1, \ldots, k_m\}$ 表示所有满足条件的整数 $0 \leq k_j < N$ 的集合，其中存在一个合法的算法输出 $A_0, \ldots, A_{N-1}$，使得对于所有 $0 \leq i < N$ 有 $A_i = B_{(i + k_j) \bmod N}$。在一行中输出两个整数 $m$ 和 $\sum_{i=1}^{m} k_i \pmod{998\,244\,353}$，以空格分隔。

特别地，如果 $S = \emptyset$，则输出 0 0。

5 3
1 2 0 0 1
0 2
1 3
3 2

1 4
1 1
1 2
1 2

提示

样例 1 解释

数组 $A$ 为 $[1, 1, 2, 0, 0]$；可以证明这是唯一对应 $B = [1, 2, 0, 0, 1]$ 的合法算法输出。一种可能的算法输入如下：

$\begin{aligned} R_1 &= \{2\} \\ R_2 &= \{3\} \\ R_3 &= \{4, 5\} \\ R_4 &= \varnothing \\ R_5 &= \varnothing. \end{aligned}$

交换 $B_0$ 和 $B_2$ 后，得到数组

$B = [0, 2, 1, 0, 1].$

可以证明唯一对应此数组的合法算法输出为

$A = [2, 1, 0, 1, 0].$

一种可能的算法输入如下：

$\begin{aligned} R_1 &= \{2, 3\} \\ R_2 &= \{4\} \\ R_3 &= \varnothing \\ R_4 &= \{5\} \\ R_5 &= \varnothing. \end{aligned}$

以下表格展示了 25 分的分布情况：

翻译由 DeepSeek V3 完成