Canadian Computing Olympiad 2025: Day 2, Problem 1

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,\ell_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 = \varnothing~ 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?

Input Specification

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}~.

The following table shows how the available 25 marks are distributed:

Marks Awarded	Bounds on ~N~	Bounds on ~Q~
3 marks	~1 \le N \le 8~	~Q = 0~
7 marks	~1 \le N \le 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~

Output Specification

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 = \varnothing~, your output should be 0 0.

Sample Input

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

Sample Output

1 4
1 1
1 2
1 2

Explanation of Output for Sample Input

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: $$\displaystyle \begin{align*} R_1 &= \{2\} \\ R_2 &= \{3\} \\ R_3 &= \{4,5\} \\ R_4 &= \varnothing \\ R_5 &= \varnothing. \end{align*}$$

After swapping ~B_0~ and ~B_2~, we get the array $$\displaystyle B = [0, 2, 1, 0, 1].$$ It can be shown the only valid output of K's algorithm that corresponds to this is $$\displaystyle A = [2, 1, 0, 1, 0].$$ One possible input to K's algorithm that yields this array ~A~ is $$\displaystyle \begin{align*} R_1 &= \{2, 3\} \\ R_2 &= \{4\} \\ R_3 &= \varnothing \\ R_4 &= \{5\} \\ R_5 &= \varnothing. \end{align*}$$