Разработка микросхем

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

Логическая схема представляет собой ациклический ориентированный граф, каждая вершина которого представляет собой либо вход, либо выход, либо логический элемент. Входы логической схемы не имеют входящих ребер и могут иметь несколько исходящих. Выходы логической схемы не имеют исходящих ребер и имеют ровно одно входящее. В данной задаче рассматриваются следующие виды логических элементов: <<или>> (or), <<и>> (and) и <<не>> (not). Элементы <<или>> и <<и>> имеют ровно два входящих ребра и могут иметь любое количество выходящих ребер, элемент <<не>> имеет ровно одно входящее ребро и может иметь любое количество исходящих ребер.

Если в графе есть ребро $uv$, то вершина $u$ называется предшественником вершины $v$.

Каждая вершина может иметь одно из двух логических значений: 0 или 1. Значения входов схемы являются ее параметрами --- это <<входные данные>>, передаваемые схеме. Значения остальных вершин вычисляются следующим образом.

Выход логической схемы имеет ровно одного предшественника, его значение равно значению предшественника.

Элемент <<или>> равен 1, если хотя бы один из его предшественников равен 1.

Элемент <<и>> равен 1, если оба его предшественника равны 1.

Элемент <<не>> равен 1, если его предшественник равен 0.

Поскольку граф является ациклическим, приведенное описание однозначно задает значения всех вершин при известных значениях входов логической схемы.

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

Например, рассмотрим схему, приведенную на следующем рисунке.

Если изменить значения на входах с $(0, 1)$ на $(1, 0)$, и первый вход изменит свое значение с 0 на 1 до того, как второй вход изменит свое значение с 1 на 0, это может привести к тому, что верхний выход схемы будет временно содержать 1, хотя он должен быть равен 0 и для начальных и для конечных значений входов.

Еще более неожиданные эффекты могут возникнуть из-за задержек, связанных с конечностью распространения сигналов по проводам. Рассмотрим схему, приведенную на следующем рисунке.

Кажется, что паразитные значения возникнуть не могут --- какой бы вход не изменил свое значение первым, на выходе будет 0. Но это не так. Пусть снова входы схемы меняются с $(0, 1)$ на $(1, 0)$. Пусть оба входа изменяют свое значение одновременно, но расстояние от верхнего входа до элемента <<и>> намного меньше, чем до элемента <<или>>. Наоборот, пусть расстояние от нижнего входа до элемента <<и>> намного больше, чем до элемента <<или>>. Тогда <<и>> <<узнает>> об изменении верхнего входа раньше, чем об изменении нижнего и переключается на 1. Аналогично, <<или>> узнает об изменении нижнего входа раньше чем об изменении верхнего и переключается на 0. Элемент <<не>> изменяет значение на 1, и наконец самый правый элемент <<и>> и выход схемы изменяют свое значение на 1. Затем информация о переключениях постепенно <<доходит>> до всех элементов и они переключаются в правильные значения.

Чтобы формализовать описанный процесс, будем считать, что каждое ребро графа может иметь различные значения в начале и в конце. Когда изменяется значение в начале ребра, значение в конце ребра может измениться не сразу, а через некоторое время.

Рассмотрим логическую схему. Вам заданы начальные и конечные значения на всех входах схемы. Процесс изменения значений остальных вершин схемы называется ее переключением. В процессе переключения следующие события могут происходить в любом порядке:

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

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

Для каждого выхода схемы можно найти ее начальное значение $i$ и конечное значение $f$. Рассмотрим значение в этой вершине перед переключением и после каждого события в процессе переключения. Выход схемы называется безопасным (safe), если его значение равно $i$ до некоторого события, и затем равно $f$ до окончания переключения (в частности, если $i=f$, то значение выхода вообще не должно меняться). Если для некоторой последовательности событий поведение значения на выходе иное, то выход называется небезопасным.

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

Первая строка входного файла содержит число $n$ --- количество вершин в логической схеме ($2 \le n \le 1200$). Следующие $n$ строк описывают вершины. Каждая вершина описывается следующим образом: сначала указан тип вершины: <<in>>, <<out>>, <<and>>, <<or>> или <<not>>.

Если тип вершины --- <<in>>, то ее описание состоит из двух целых чисел, каждое из которых равно 0 или 1: начального и конечного значения на входе.

Если вершина имеет тип <<out>> или <<not>>, то ее описание состоит из одного числа --- номера ее предшественника.

Если вершина имеет тип <<and>> или <<or>>, то ее описание состоит из двух чисел --- номеров ее предшественников.

Вершины нумеруются от 1 до $n$ в порядке, в котором они заданы во входном файле. Предшественники вершины всегда имеют номер, не превышающий номера вершины.

Для каждого выхода выведите, является ли он безопасным, следуя формату, приведенному в примере.