Andrea 提出了一种他认为是针对长度 $$$n$$$ 的数组的新颖排序算法。该算法的工作原理如下。
最初有一个 $$$n$$$ 整数数组 $$$a_1,\, a_2,\, \dots,\, a_n$$$。然后,执行 $$$k$$$ 步骤。
对于每个 $$$1\le i\le k$$$,在第 $$$i$$$ 步骤中,对索引为 $$$j_{i,1}< j_{i,2}< \dots< j_{i, q_i}$$$ 的数组 $$$a$$$ 的子序列进行排序,而不更改其余索引的值。因此,子序列 $$$a_{j_{i,1}},\, a_{j_{i,2}},\, \dots,\, a_{j_{i,q_i}}$$$ 已排序,并且 $$$a$$$ 的所有其他元素保持不变。
Andrea 急于与学术界分享他的发现,向《排序算法年鉴》杂志发送了一篇描述他的算法的短论文,而你是这篇论文的审稿人(即必须判断论文正确性的人)。您必须确定 Andrea 的算法是否正确,即它是否对 $$$n$$$ 整数的任意数组 $$$a$$$ 进行排序。
输入
第一行包含两个整数 $$$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}<j_{i,2}<\cdots<j_{i,q_i}\le n$$$) — 第 $$$i$$$ 步骤中考虑的子序列的长度以及子序列的索引。
输出
如果 Andrea 的算法正确,则打印 ACCEPTED,否则打印 REJECTED。
示例
输入 #1
4 3 3 1 2 3 3 2 3 4 2 1 2
输出 #1
ACCEPTED
输入 #2
4 3 3 1 2 3 3 2 3 4 3 1 3 4
输出 #2
REJECTED
输入 #3
3 4 1 1 1 2 1 3 2 1 3
输出 #3
REJECTED
输入#4
5 2 3 2 3 4 5 1 2 3 4 5
输出#4
ACCEPTED
注意
第一个示例的说明:该算法由 $$$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$$$ 将被排序。