P12969 [CCO 2025] Restaurant Recommendation Rescue

A certain aspiring musician K loves going for shabu-shabu! Recently, she's been to $N$ shabu-shabu restaurants, numbered $1, 2, \ldots, N$, following the following algorithm: 1. K keeps an ordered list of recommendations, starting with restaurant 1. 2. On the $i$-th day, she visits the next recommended restaurant on her list, which recommends her restaurants $R_i = \{r_{i,1}, \ldots, r_{i,l_i}\}$. 3. K appends $R_i$ to her list of restaurants to visit. 4. K repeats steps 2-4 until she runs out of recommended restaurants. 5. K writes down the array $A_0, \ldots, A_{N-1}$, where $A_i$ equals the number of restaurants she was recommended on the $(i+1)$-th day. That is, $A_i = |R_{i+1}|$. It is guaranteed that $\bigcup_{i=1}^{N} R_i = \{2, \ldots, N\}$ and $R_i \cap R_j = \emptyset$ for $i \neq j$, that is, every restaurant, other than the first, will be recommended by exactly one other restaurant. Once K finishes her list, K's delinquent friend H decides to play a prank on her! She replaces the array $A_0, \ldots, A_{N-1}$ with another array $B_0, \ldots, B_{N-1}$! K thinks that this new array $B_i$ might just be a cyclic shift of her array, so she asks you to determine all possible $0 \leq k < N$ such that $A_i = B_{(i+k) \bmod N}$, for all $0 \leq i < N$ and any valid output of her algorithm $A_0, \ldots, A_{N-1}$. Furthermore, K will then perform $Q$ operations, where for the $i$-th operation, she swaps $B_{x_i}, B_{y_i}$ and asks you to do the same on the new array. Can you help K see through her friend's prank?

The first line of input will contain two integers, $N$ ($1 \leq N \leq 500\,000$) and $Q$ ($0 \leq Q \leq 300\,000$). The next line of input will contain $N$ space-separated non-negative integers, $B_0, B_1, \ldots, B_{N-1}$ ($0 \leq B_i < N$), the initial sequence. The $i$-th of the next $Q$ lines of input will contain two integers each, $x_i$ and $y_i$ ($0 \leq x_i, y_i < N$ and $x_i \neq y_i$), indicating you are to swap $B_{x_i}$ with $B_{y_i}$.

For each of the $Q + 1$ arrays (including the initial array $B_0, \ldots, B_{N-1}$), let $S = \{k_1, \ldots, k_m\}$ denote the set of integers $0 \leq k_j < N$ such that there exists a valid output $A_0, \ldots, A_{N-1}$ of K's algorithm such that $A_i = B_{(i + k_j) \bmod N}$ for all $0 \leq i < N$. Output, on a single line, the integers $m$ and $\sum_{i=1}^{m} k_i \pmod{998\,244\,353}$, separated by a space. In particular, if $S = \emptyset$, your output should be `0 0`.

**Sample 1 Explanation** The array $A$ is $[1, 1, 2, 0, 0]$; it can be shown this is the only valid output of K's algorithm that corresponds to the array $B = [1, 2, 0, 0, 1]$. One input for K's algorithm that yields this array $A$ is: $\begin{aligned} R_1 &= \{2\} \\ R_2 &= \{3\} \\ R_3 &= \{4, 5\} \\ R_4 &= \varnothing \\ R_5 &= \varnothing. \end{aligned}$ After swapping $B_0$ and $B_2$, we get the array $B = [0, 2, 1, 0, 1].$ It can be shown the only valid output of K's algorithm that corresponds to this is $A = [2, 1, 0, 1, 0].$ One possible input to K's algorithm that yields this array $A$ is $\begin{aligned} R_1 &= \{2, 3\} \\ R_2 &= \{4\} \\ R_3 &= \varnothing \\ R_4 &= \{5\} \\ R_5 &= \varnothing. \end{aligned}$ The following table shows how the available $25$ marks are distributed: | Marks Awarded | Bounds on $N$ | Bounds on $Q$ | |:---------------:|:----------------:|:----------------:| | 3 marks | $1 \leq N \leq 8$ | $Q = 0$ | | 7 marks | $1 \leq N \leq 5\,000$ | $Q = 0$ | | 10 marks | $1 \leq N \leq 500\,000$ | $Q = 0$ | | 5 marks | $1 \leq N \leq 500\,000$ | $0 \leq Q \leq 300\,000$ |