P12969 [CCO 2025] Restaurant Recommendation Rescue

一位有抱负的音乐家 **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`。

**样例 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 分的分布情况： | 分值 | $N$ 的范围 | $Q$ 的范围 | |:------:|:-------------------:|:-----------------------:| | 3 分 | $1 \leq N \leq 8$ | $Q = 0$ | | 7 分 | $1 \leq N \leq 5\,000$ | $Q = 0$ | | 10 分 | $1 \leq N \leq 500\,000$ | $Q = 0$ | | 5 分 | $1 \leq N \leq 500\,000$ | $0 \leq Q \leq 300\,000$ | 翻译由 DeepSeek V3 完成