A Serious Referee
Contest: Codeforces Global Round 15
Difficulty rating: 3000
Tags: bitmasks, brute force, dfs and similar, sortings

Andrea has come up with what he believes to be a novel sorting algorithm for arrays of length $$$n$$$. The algorithm works as follows.

Initially there is an array of $$$n$$$ integers $$$a_1,\, a_2,\, \dots,\, a_n$$$. Then, $$$k$$$ steps are executed.

For each $$$1\le i\le k$$$, during the $$$i$$$-th step the subsequence of the array $$$a$$$ with indexes $$$j_{i,1}< j_{i,2}< \dots< j_{i, q_i}$$$ is sorted, without changing the values with the remaining indexes. So, the subsequence $$$a_{j_{i,1}},\, a_{j_{i,2}},\, \dots,\, a_{j_{i,q_i}}$$$ is sorted and all other elements of $$$a$$$ are left untouched.

Andrea, being eager to share his discovery with the academic community, sent a short paper describing his algorithm to the journal "Annals of Sorting Algorithms" and you are the referee of the paper (that is, the person who must judge the correctness of the paper). You must decide whether Andrea's algorithm is correct, that is, if it sorts any array $$$a$$$ of $$$n$$$ integers.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1\le n\le 40$$$, $$$0\le k\le 10$$$) — the length of the arrays handled by Andrea's algorithm and the number of steps of Andrea's algorithm.

Then $$$k$$$ lines follow, each describing the subsequence considered in a step of Andrea's algorithm.

The $$$i$$$-th of these lines contains the integer $$$q_i$$$ ($$$1\le q_i\le n$$$) followed by $$$q_i$$$ integers $$$j_{i,1},\,j_{i,2},\,\dots,\, j_{i,q_i}$$$ ($$$1\le j_{i,1}<j_{i,2}<\cdots<j_{i,q_i}\le n$$$) — the length of the subsequence considered in the $$$i$$$-th step and the indexes of the subsequence.

Output format:
If Andrea's algorithm is correct print ACCEPTED, otherwise print REJECTED.

Constraints:
Time limit: 1.0 s
Memory limit: 512.0 MB

Note:
Explanation of the first sample: The algorithm consists of $$$3$$$ steps. The first one sorts the subsequence $$$[a_1, a_2, a_3]$$$, the second one sorts the subsequence $$$[a_2, a_3, a_4]$$$, the third one sorts the subsequence $$$[a_1,a_2]$$$. For example, if initially $$$a=[6, 5, 6, 3]$$$, the algorithm transforms the array as follows (the subsequence that gets sorted is highlighted in red) $$$$$$ [{\color{red}6},{\color{red}5},{\color{red}6},3] \rightarrow [5, {\color{red}6}, {\color{red}6}, {\color{red}3}] \rightarrow [{\color{red}5}, {\color{red}3}, 6, 6] \rightarrow [3, 5, 6, 6] \,.$$$$$$ One can prove that, for any initial array $$$a$$$, at the end of the algorithm the array $$$a$$$ will be sorted.

Explanation of the second sample: The algorithm consists of $$$3$$$ steps. The first one sorts the subsequence $$$[a_1, a_2, a_3]$$$, the second one sorts the subsequence $$$[a_2, a_3, a_4]$$$, the third one sorts the subsequence $$$[a_1,a_3,a_4]$$$. For example, if initially $$$a=[6, 5, 6, 3]$$$, the algorithm transforms the array as follows (the subsequence that gets sorted is highlighted in red) $$$$$$ [{\color{red}6},{\color{red}5},{\color{red}6},3] \rightarrow [5, {\color{red}6}, {\color{red}6}, {\color{red}3}] \rightarrow [{\color{red}5}, 3, {\color{red}6}, {\color{red}6}] \rightarrow [5, 3, 6, 6] \,.$$$$$$ Notice that $$$a=[6,5,6,3]$$$ is an example of an array that is not sorted by the algorithm.

Explanation of the third sample: The algorithm consists of $$$4$$$ steps. The first $$$3$$$ steps do nothing because they sort subsequences of length $$$1$$$, whereas the fourth step sorts the subsequence $$$[a_1,a_3]$$$. For example, if initially $$$a=[5,6,4]$$$, the algorithm transforms the array as follows (the subsequence that gets sorted is highlighted in red) $$$$$$ [{\color{red}5},6,4] \rightarrow [5,{\color{red}6},4] \rightarrow [5,{\color{red}6},4] \rightarrow [{\color{red}5},6,{\color{red}4}]\rightarrow [4,6,5] \,.$$$$$$ Notice that $$$a=[5,6,4]$$$ is an example of an array that is not sorted by the algorithm.

Explanation of the fourth sample: The algorithm consists of $$$2$$$ steps. The first step sorts the subsequences $$$[a_2,a_3,a_4]$$$, the second step sorts the whole array $$$[a_1,a_2,a_3,a_4,a_5]$$$. For example, if initially $$$a=[9,8,1,1,1]$$$, the algorithm transforms the array as follows (the subsequence that gets sorted is highlighted in red) $$$$$$ [9,{\color{red}8},{\color{red}1},{\color{red}1},1] \rightarrow [{\color{red}9},{\color{red}1},{\color{red}1},{\color{red}8},{\color{red}1}] \rightarrow [1,1,1,8,9] \,.$$$$$$ Since in the last step the whole array is sorted, it is clear that, for any initial array $$$a$$$, at the end of the algorithm the array $$$a$$$ will be sorted.

Example input:
4 3
3 1 2 3
3 2 3 4
2 1 2

Example output:
ACCEPTED

Example input:
4 3
3 1 2 3
3 2 3 4
3 1 3 4

Example output:
REJECTED

Editorial:
Let us say that an array of $$$n$$$ integers is good if it is sorted by Andrea's algorithm, and bad otherwise.
First of all, we state and prove the following intuitive fact (which is well-known for sorting networks):
Lemma. (Zero-One Principle) All arrays $$$a$$$ with values in $$$\{0, \, 1\}$$$ are good if and only if all arrays are good.
Proof. The "if" part is trivial.
To prove the converse, consider an array $$$a$$$ made up of arbitrary integers (for simplicity, we assume that they are distinct). Fix some $$$1 \le s \le n$$$ and construct the array $$$b$$$ such that $$$b_i = 0$$$ if $$$a_i$$$ is among the $$$s$$$ smallest elements of $$$a$$$, and $$$b_i = 1$$$ otherwise. Since we know that $$$b$$$ is good, it follows that Andrea's algorithm applied on $$$a$$$ will produce an array in which the $$$s$$$ smallest elements occupy the first $$$s$$$ positions.
Since this is true for every $$$s \in \{1, \, 2, \, \dots, \, n\}$$$, we deduce that $$$a$$$ is good.
If $$$n = 1$$$, then the answer is always ACCEPTED. From now on, we assume $$$n \ge 2$$$.
Let $$$S_i = \{j_{i,1}, \, \dots, \, j_{i,q_i}\}$$$ be the set of indices considered in the $$$i$$$-th step. Let $$$T_i = S_1 \cup S_2 \cup \cdots \cup S_i$$$.
Given a function $$$f: T_i \to \{0, \, 1\}$$$, we say that it is $$$i$$$-achievable if there is an initial array $$$a_1, \, a_2, \, \dots, \, a_n \in \{0, \, 1\}$$$ so that, after $$$i$$$ steps, $$$a_j = f(j)$$$ holds for each $$$j \in T_i$$$. Applying the Zero-One Principle, one can show that the answer to the problem is ACCEPTED if and only if $$$T_k = \{1, \, 2, \, \dots, \, n\}$$$ and all the $$$k$$$-achievable functions are nondecreasing (there are $$$n + 1$$$ nondecreasing functions, which are those like $$$(0,0,\dots,0,1,\dots,1,1)$$$).
The idea, then, is to compute, for each $$$i = 1, \, 2, \, \dots, \, k$$$, the set of $$$i$$$-achievable functions. Let $$$f: T_i \to \{0, \, 1\}$$$ be an $$$i$$$-achievable function. Notice that, for each $$$g: S_{i+1} \setminus T_i \to \{0, \, 1\}$$$, we can find an initial configuration such that after $$$i$$$ steps it coincides with $$$f$$$ on $$$T_i$$$ and with $$$g$$$ on $$$S_{i + 1} \setminus T_i$$$. In particular, we can choose arbitrarily how many times the function $$$g$$$ takes the value $$$1$$$.
The crucial observation is that if we know $$$f$$$ and we know how many times the function $$$g$$$ takes the value $$$1$$$, then we know unambiguously what happens on $$$T_{i + 1}$$$ after $$$i + 1$$$ steps: on $$$T_{i + 1} \setminus S_{i + 1}$$$ the values are exactly the values of $$$f$$$, on $$$S_{i + 1}$$$ the values are nondecreasing and thus only the number of ones is necessary to determine them.
Thus, given an $$$i$$$-achievable function, we can construct the $$$(i + 1)$$$-achievable functions it can evolve into and there are exactly $$$|S_{i + 1} \setminus T_i| + 1$$$ of them.
Let $$$d_i = |S_i \setminus T_{i - 1}|$$$. The complexity of the described algorithm is $$$O(n \cdot (d_1 + 1)(d_2 + 1) \cdots (d_k + 1))$$$. Since $$$(d_1 + 1) + (d_2 + 1) + \cdots + (d_k + 1) \le n + k$$$, we have (by the AM-GM inequality): $$$$$$ (d_1 + 1)(d_2 + 1) \cdots (d_k + 1) \le \left(\frac{n + k}{k}\right)^k. $$$$$$ Thus the complexity turns out to be $$$O\left(n\left(\frac{n + k}{k}\right)^k\right)$$$. Depending on the implementation, this might or might not fit into the time-limit.
Here are three observations which reduce hugely the execution time (the first one is already sufficient to fit into the time-limit comfortably):
1. It is possible to encode the $$$i$$$-achievable functions as bitmasks and all the steps of the solutions can be performed as bitwise operations.
2. Let us show that if $$$T_{k - 1} \ne \{1, \, 2, \, \dots, \, n\}$$$ and $$$S_k \ne \{1, \, 2, \, \dots, \, n\}$$$, then the answer is REJECTED. Let $$$x \not\in T_{k - 1}$$$ and $$$y \not\in S_k$$$. If $$$x = y$$$, then $$$x \not\in T_k$$$ and we already know that the answer is REJECTED. Otherwise, let $$$a$$$ be a permutation of $$$1, \, 2, \, \dots, \, n$$$ with $$$a_x = y$$$. After $$$k - 1$$$ steps it still holds $$$a_x = y$$$ and after $$$k$$$ steps $$$y \in \{a_j: j \in S_k\}$$$ which implies that $$$a_y \ne y$$$ and therefore the array is not sorted by the algorithm. With this observation (together with the above described usage of bitmasks), the complexity of the algorithm becomes $$$O\left(\left(\frac{n + k - 1}{k - 1}\right)^{k - 1}\right)$$$.
3. To save a lot of memory (and, since memory allocation is expensive, also execution time), one can implement the algorithm in a recursive fashion.
Complexity: $$$O\left(n\left(\frac{n + k}{k}\right)^k\right)$$$.