Вирусы

Одной из важнейших задач современной информатики является моделирование биологических процессов. Недавно биологи обнаружили 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 не обладает ни тем, ни другим свойством.

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

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