Задача L. Лишние вопросы
Задачу добавил: alef
Успешно сдано решений: 22
У Стива появилось достаточно много вопросов. Пожалуй, он хотел бы, чтобы их задали менеджерам Quantum Artificial Intelligence.
Стив полагает, что составил вопросы таким образом, что на каждый из них можно ответить либо «Да», либо «Нет», либо «Без комментариев».
Стив хочет, чтобы вопросы были заданы в определённой последовательности. Кроме того, по его мнению, на некоторые вопросы он может получить ответ косвенно. Для таких вопросов он определил вопросы-предпосылки.
Пусть для вопроса #j предпосылками являются вопросы с номерами k1, k2, ..., kmj (все номера меньше j). Если к моменту, когда подойдёт очередь задавать вопрос #j, более чем на половину вопросов-предпосылок будет получен ответ «Да», Стив не станет задавать этот вопрос, а просто отметит, что ответом на него также было «Да». Аналогично, если более чем на половину вопросов-предпосылок будет получен ответ «Нет», Стив также не станет задавать этот вопрос и отметит, что ответом на этот вопрос было «Нет». В любом другом случае Стив задаст этот вопрос.
Когда Стив анализирует ответы на вопросы-предпосылки, для него не важно, как именно были получены ответы на эти вопросы — непосредственно от менеджеров или же в результате его собственных логических построений.
В параллельной вселенной даром предвидения наделён не только Стив, но и менеджеры Quantum Artificial Intelligence. Поэтому они уже знают, как ответят на каждый из вопросов.
Если Стив решил не задавать какой-либо вопрос и сформировал ответ на него самостоятельно, то даже если ответ Стива не совпадает с (возможным) ответом менеджеров, он учитывает именно «свой» ответ.
Ваша задача — определить, сколько вопросов задаст Стив и какие это будут вопросы.
В первой строке содержатся целые числа n и p (1 ≤ n ≤ 1000, 0 ≤ p ≤ n - 1) — общее количество вопросов и количество вопросов, имеющих вопросы-предпосылки.
Во второй строке содержится последовательность из n символов Y, N, C, означающих соответственно ответы «Да», «Нет», «Без комментариев».
Далее следуют p строк, каждая из которых описывает по одному вопросу с его предпосылками в следующем формате: номер j вопроса (1 ≤ j ≤ n), имеющего предпосылки, их количество mj (1 ≤ mj ≤ j - 1), и собственно номера самих вопросов-предпосылок k1, k2, ..., kmj (1 ≤ k1 < k2... < kmj < j, mj < j).
Гарантируется, что каждый номер вопроса встречается в описаниях не более одного раза.
В первой строке выведите единственное целое число — количество вопросов, которые задаст Стив.
Во второй строке выведите номера этих вопросов в порядке возрастания.
8 5
YNCNCYNY
2 1 1
7 2 1 6
4 3 1 2 3
5 2 2 4
8 2 3 5
4
1 3 6 8