题目描述

译自 CCO 2025 Day2 T1「Restaurant Recommendation Rescue」。

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

1. K 维护一个推荐餐厅的有序列表，初始时只有餐厅 $1$。
2. 在第 $i$ 天，她访问列表中下一个推荐的餐厅，该餐厅会推荐给她一组餐厅 $R_{i} = \{r_{i,1}, \ldots, r_{i,\ell_{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\}$ 且对于 $i \neq j$，$R_{i} \cap R_{j} = \varnothing$，也就是说，除了第一个餐厅外，每个餐厅都恰好被另一个餐厅推荐一次。

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

此外，K 随后会进行 $Q$ 次操作，在第 $i$ 次操作中，她交换 $B_{x_{i}}$ 和 $B_{y_{i}}$，并要求你对新数组执行相同的操作。你能帮助 K 识破她朋友的恶作剧吗？

输入格式

第一行包含两个整数，$N$ $(1 \leq N \leq 500000)$ 和 $Q$ $(0 \leq Q \leq 300000)$。

第二行包含 $N$ 个用空格分隔的非负整数，$B_{0}, B_{1}, \ldots, B_{N-1}$ $(0 \leq B_{i} < N)$，表示初始序列。

接下来的 $Q$ 行中，第 $i$ 行包含两个整数 $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$ 的整数集合，使得存在 K 的算法的一个合法输出 $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 {998244353}$，用空格分隔。

特别地，如果 $S = \varnothing$，你的输出应为 0 0。

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

1 4
1 1
1 2
1 2

数组 $A$ 为 $[1, 1, 2, 0, 0]$；可以证明这是唯一对应于数组 $B=[1, 2, 0, 0, 1]$ 的 K 的算法合法输出。K 的算法的一个输入示例为：

$$\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] .$$

可以证明唯一对应于此的 K 的算法有效输出为

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

K 的算法的一个可能输入为

$$\begin{aligned} & R_{1}=\{2, 3\} \\ & R_{2}=\{4\} \\ & R_{3}=\varnothing \\ & R_{4}=\{5\} \\ & R_{5}=\varnothing . \end{aligned} $$

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	分值	$N$ 的限制	$Q$ 的限制
$1$	$12$	$1 \leq N \leq 8$	$Q=0$
$2$	$28$	$1 \leq N \leq 5000$
$3$	$40$	$1 \leq N \leq 500000$
$4$	$20$		$0 \leq Q \leq 300000$