22158번 - Задачи 스페셜 저지다국어

문제

При подготовке соревнований по программированию одна из проблем, встающих перед организаторами — выбор задач, которые будут в этом соревновании. Чтобы соревнование было интересным, необходимо, чтобы задачи в нем были разной сложности. Также, необходимо, чтобы задачи были на разные темы. Ведь кому интересно решать одинаковые задачи? К счастью, у организаторов есть множество задач, и им есть, из чего выбирать.

У вас есть несколько задач. Для каждой задачи известна ее уровень сложости — целое число, и то, какие темы она затрагивает. Вам нужно выбрать такое подмножество задач, чтобы выполнялись следующие требования:

• Выбрана ровно одна задача каждого уровня сложности
• Каждая тема представлена
• Никакие две задачи не пересекаются по темам

Сформируйте из имеющихся у вас задач набор задач на соревнование, удовлетворяющий написанным выше требованиям.

입력

Первая строка содержит три целых числа n (1 ≤ n ≤ 300) — количество задач, d (1 ≤ d ≤ 50) — количество уровней сложности задач и m (1 ≤ m ≤ 18) — количество различных тем. Далее, в n строках задается описание задач.

Каждая задача задается в следующем формате: c_i k_i t_i1 t_i2 ... t_iki, где c_i (1 ≤ c_i ≤ d) — сложность i-й задачи, k_i (0 ≤ k_i ≤ m) — количество тем, которые затрагивает данная задача, t_ij (1 ≤ t_ij ≤ m) — темы, которые затрагивает i-я задача. Внутри одной задачи все t_ij различны.

출력

Выведите в первой строке «OK», если требуемый набор задач найден, и «Impossible» в противном случае. Если ответ есть, выведите в следующей строке d целых чисел — номера задач, которые входят в требуемый набор.

제한

힌트