20447번 - Вирусы 서브태스크다국어

Одной из важнейших задач современной информатики является моделирование биологических процессов. Недавно биологи обнаружили $n$ вирусов, каждому из которых был присвоен уникальный кодовый номер от $1$ до $n$. Вирус обладает возможностью встраиваться в клетки других организмов. Изначально в распоряжении ученых находятся $n$ клеток, пронумерованных от $1$ до $n$, при этом клетка с номером $i$ заражена вирусом $i$. Каждая клетка может быть заражена только одним вирусом.

Для каждой клетки был установлен уровень её восприимчивости к каждому из вирусов. А именно, для каждой клетки известен вирус, к которому она наиболее восприимчива, к какому из оставшихся вирусов она наиболее восприимчива, и так далее.

Зараженные вирусами клетки атакуют друг друга. Пусть клетка с номером $i$ сейчас заражена вирусом с номером $a$ и атакует клетку с номером $j$, которая заражена вирусом с номером $b$. Тогда, если клетка с номером $j$ является более восприимчивой к вирусу $a$, чем к вирусу $b$, то клетка с номером $j$ становится заражена вирусом $a$.

В эксперименте ученые помещают все $n$ клеток в замкнутую среду, в результате чего клетки могут атаковать друг друга произвольным образом. Эксперимент завершается, когда в результате таких атак ни для какой клетки не может измениться вирус, которым она заражена.

Ученые называют вирус с номером $i$ стабильным, если при любой последовательности атак клетками друг друга, приводящей к завершению эксперимента, останется хотя бы одна клетка, зараженная вирусом с номером $i$.

Ученые называют вирус с номером $i$ жизнеспособным, если существует такая последовательность атак клетками друг друга, приводящая к завершению эксперимента, после которой останется хотя бы одна клетка, зараженная вирусом с номером $i$.

Например, пусть есть два вируса, при этом клетка номер 1 наиболее восприимчива к вирусу номер 1, а клетка с номером 2 --- наиболее восприимчива к вирусу номер 2. Тогда эксперимент завершается сразу: любая атака не приводит к изменению того, каким вирусом заражена клетка. Таким образом оба вируса являются стабильными и жизнеспособными.

Пусть теперь есть два вируса, но клетка с номером 1 наиболее восприимчива к вирусу с номером 2, а клетка с номером 2 --- к вирусу с номером 1. Тогда эксперимент завершается после любой атаки одной клеткой другой. Возможны два сценария. В первом сценарии клетка 1 атакует клетку 2, обе клетки становятся заражены вирусом 1. Во втором сценарии клетка 2 атакует клетку 1, после этого обе клетки становятся заражены вирусом 2. Таким образом, стабильных вирусов нет, но оба вируса являются жизнеспособными.

Наконец, пусть есть два вируса, и обе клетки более восприимчивы к вирусу с номером 1. Тогда атака клеткой 2 клетки 1 не приводит к изменению вируса, которым она заражена, а если клетка 1 атакует клетку 2, то вторая клетка становится зараженной вирусом 1. Следовательно эксперимент завершится после атаки клетки 1 клеткой 2, вирус 1 является стабильным и жизнеспособным, а вирус 2 не обладает ни тем, ни другим свойством.

Ученым необходимо отвечать на два типа вопросов, какие вирусы являются стабильными и какие вирусы являются жизнеспособными.

Требуется написать программу, которая по описанию клеток и типу вопроса определяет все стабильные, либо все жизнеспособные вирусы.

В первой строке входных данных содержится целое число $n$ --- количество вирусов и, соответственно, клеток ($1 \le n \le 500$).

Далее в $n$ строках содержатся описания клеток. Для каждой клетки указано $n$ различных чисел от $1$ до $n$: номера вирусов в порядке убывания восприимчивости к ним этой клетки.

Последняя строка содержит число $p$, которая задаёт свойство вирусов, которое интересует ученых. Значение $p = 1$ означает, что ученые хотят определить все стабильные вирусы, а значение $p = 2$ означает, что ученые хотят определить все жизнеспособные вирусы.

Первая строка выходных данных должна содержать целое $k$ --- количество вирусов, которые обладают интересующим ученых свойством ($0 \le k \le n$).

Вторая строка должна содержать $k$ целых чисел --- номера вирусов, обладающих этим свойством. Номера вирусов необходимо выводить в возрастающем порядке.