G. Серьезный судья
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Андреа придумал, как он считает, новый алгоритм сортировки для массивов длины $$$n$$$. Алгоритм работает следующим образом.

Изначально имеется массив из $$$n$$$ целых чисел $$$a_1,\, a_2,\, \dots,\, a_n$$$. Затем выполняется $$$k$$$ шагов.

Для каждого $$$1\le i\le k$$$ на $$$i$$$-м шаге сортируется подпоследовательность массива $$$a$$$ с индексами $$$j_{i,1}< j_{i,2}< \dots< j_{i, q_i}$$$, не меняя значений с остальными индексами. Таким образом, в результате подпоследовательность $$$a_{j_{i,1}},\, a_{j_{i,2}},\, \dots,\, a_{j_{i,q_i}}$$$ отсортирована, а все остальные элементы $$$a$$$ остались нетронутыми.

Андреа, желая поделиться своим открытием с научным сообществом, отправил небольшую статью с описанием своего алгоритма в журнал «Анналы алгоритмов сортировки», а вы являетесь рецензентом статьи (то есть человеком, который должен оценить правильность статьи). Вы должны решить, является ли алгоритм Андреа правильным, то есть сортирует ли он любой массив $$$a$$$ из $$$n$$$ целых чисел.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1\le n\le 40$$$, $$$0\le k\le 10$$$) — длину массивов, обрабатываемых алгоритмом Андреа, и количество шагов алгоритма Андреа.

Далее следуют $$$k$$$ строк, каждая из которых описывает подпоследовательность, рассматриваемую на одном из шагов алгоритма Андреа.

В $$$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$$$-м шаге, и индексы подпоследовательности.

Выходные данные

Если алгоритм Андреа верен, выведите ACCEPTED, иначе выведите REJECTED.

Примеры
Входные данные
4 3
3 1 2 3
3 2 3 4
2 1 2
Выходные данные
ACCEPTED
Входные данные
4 3
3 1 2 3
3 2 3 4
3 1 3 4
Выходные данные
REJECTED
Входные данные
3 4
1 1
1 2
1 3
2 1 3
Выходные данные
REJECTED
Входные данные
5 2
3 2 3 4
5 1 2 3 4 5
Выходные данные
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$$$ будет отсортирован.