CF1552G.A Serious Referee

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} \lt j_{i,2} \lt \dots \lt 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.

安德烈提出了一种他认为是全新的、用于长度为 $n$ 的数组的排序算法。该算法的工作方式如下：

初始时，给定一个由 $n$ 个整数组成的数组 $a_1,\, a_2,\, \dots,\, a_n$。随后，执行 $k$ 个步骤。

对每个 $1\le i\le k$，在第 $i$ 步中，将数组 $a$ 中下标为 $j_{i,1} \lt j_{i,2} \lt \dots \lt j_{i, q_i}$ 的子序列进行排序，而其余下标位置上的元素值保持不变。即，子序列 $a_{j_{i,1}},\, a_{j_{i,2}},\, \dots,\, a_{j_{i,q_i}}$ 被升序（或降序）排序，而数组 $a$ 中所有其他元素均保持原状。

安德烈急于将自己的发现分享给学术界，因此向期刊《排序算法年刊》（Annals of Sorting Algorithms）提交了一篇简短论文来描述该算法；而你正是这篇论文的审稿人（即负责判断该论文正确性的人）。你必须判定：安德烈的算法是否正确？也就是说，该算法是否能对任意由 $n$ 个整数组成的数组 $a$ 实现完全排序？

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} \lt j_{i,2} \lt \cdots \lt j_{i,q_i}\le n$) — the length of the subsequence considered in the $i$-th step and the indexes of the subsequence.

第一行包含两个整数 $n$ 和 $k$（$1\le n\le 40$，$0\le k\le 10$）—— 分别表示 Andrea 算法所处理的数组长度以及 Andrea 算法的步数。

接下来是 $k$ 行，每行描述 Andrea 算法中某一步所考虑的子序列。

其中第 $i$ 行包含一个整数 $q_i$（$1\le q_i\le n$），后跟 $q_i$ 个整数 $j_{i,1},\,j_{i,2},\,\dots,\, j_{i,q_i}$（$1\le j_{i,1} \lt j_{i,2} \lt \cdots \lt j_{i,q_i}\le n$）—— 分别表示第 $i$ 步所考虑子序列的长度及其下标。

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

如果安德烈亚的算法正确，则输出 ACCEPTED，否则输出 REJECTED。

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.

第一个样例的说明：该算法包含 $3$ 个步骤。第一步对子序列 $[a_1, a_2, a_3]$ 进行排序，第二步对子序列 $[a_2, a_3, a_4]$ 进行排序，第三步对子序列 $[a_1,a_2]$ 进行排序。例如，若初始数组为 $a=[6, 5, 6, 3]$，则该算法将数组按如下方式变换（每次被排序的子序列以红色高亮）：

\[{\\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\] \\,.

可以证明：对于任意初始数组 $a$，该算法执行完毕后，数组 $a$ 必然已排序。

第二个样例的说明：该算法包含 $3$ 个步骤。第一步对子序列 $[a_1, a_2, a_3]$ 进行排序，第二步对子序列 $[a_2, a_3, a_4]$ 进行排序，第三步对子序列 $[a_1,a_3,a_4]$ 进行排序。例如，若初始数组为 $a=[6, 5, 6, 3]$，则该算法将数组按如下方式变换（每次被排序的子序列以红色高亮）：

\[{\\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\] \\,.

注意：$a=[6,5,6,3]$ 是一个该算法无法将其排序的数组实例。

第三个样例的说明：该算法包含 $4$ 个步骤。前 $3$ 步不产生任何变化，因为它们分别对长度为 $1$ 的子序列进行排序；第四步对子序列 $[a_1,a_3]$ 进行排序。例如，若初始数组为 $a=[5,6,4]$，则该算法将数组按如下方式变换（每次被排序的子序列以红色高亮）：

\[{\\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\] \\,.

注意：$a=[5,6,4]$ 是一个该算法无法将其排序的数组实例。

第四个样例的说明：该算法包含 $2$ 个步骤。第一步对子序列 $[a_2,a_3,a_4]$ 进行排序，第二步对整个数组 $[a_1,a_2,a_3,a_4,a_5]$ 进行排序。例如，若初始数组为 $a=[9,8,1,1,1]$，则该算法将数组按如下方式变换（每次被排序的子序列以红色高亮）：

\[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\] \\,.

由于最后一步对整个数组进行了排序，显然：对于任意初始数组 $a$，该算法执行完毕后，数组 $a$ 必然已排序。