#P12969. [CCO 2025] Restaurant Recommendation Rescue
[CCO 2025] Restaurant Recommendation Rescue
题目描述
A certain aspiring musician K loves going for shabu-shabu! Recently, she's been to shabu-shabu restaurants, numbered , following the following algorithm:
- K keeps an ordered list of recommendations, starting with restaurant 1.
- On the -th day, she visits the next recommended restaurant on her list, which recommends her restaurants .
- K appends to her list of restaurants to visit.
- K repeats steps 2-4 until she runs out of recommended restaurants.
- K writes down the array , where equals the number of restaurants she was recommended on the -th day. That is, .
It is guaranteed that and for , 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 with another array ! K thinks that this new array might just be a cyclic shift of her array, so she asks you to determine all possible such that , for all and any valid output of her algorithm .
Furthermore, K will then perform operations, where for the -th operation, she swaps 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, () and ().
The next line of input will contain space-separated non-negative integers, (), the initial sequence.
The -th of the next lines of input will contain two integers each, and ( and ), indicating you are to swap with .
输出格式
For each of the arrays (including the initial array ), let denote the set of integers such that there exists a valid output of K's algorithm such that for all . Output, on a single line, the integers and , separated by a space.
In particular, if , your output should be 0 0
.
5 3
1 2 0 0 1
0 2
1 3
3 2
1 4
1 1
1 2
1 2
提示
Sample 1 Explanation
The array is ; it can be shown this is the only valid output of K's algorithm that corresponds to the array . One input for K's algorithm that yields this array is:
$\begin{aligned} R_1 &= \{2\} \\ R_2 &= \{3\} \\ R_3 &= \{4, 5\} \\ R_4 &= \varnothing \\ R_5 &= \varnothing. \end{aligned}$
After swapping and , we get the array
It can be shown the only valid output of K's algorithm that corresponds to this is
One possible input to K's algorithm that yields this array 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 marks are distributed:
Marks Awarded | Bounds on | Bounds on |
---|---|---|
3 marks | ||
7 marks | ||
10 marks | ||
5 marks |