Машинное обучение

Машинное обучение --- раздел теоретической информатики, который изучает возможности алгоритмов и компьютерных программ <<обучаться>>. Обычно обучение происходит с использованием так называемых обучающих примеров. В этой задаче вам предстоит реализовать простейший вариант машинного обучения, натренировав детерминированный конечный автомат правильно распознавать слова из заданного множества.

Формально детерминированный конечный автомат представляет собой набор из четырех элементов: $\langle\Sigma, U, s, T, \varphi\rangle$, где $\Sigma$ --- конечное множество, которое представляет собой входной алфавит (в этой задаче будем полагать, что $\Sigma = \{0, 1\}$), $U$ --- это некоторое конечное множество состояний, $s \in U$ --- начальное состояние, $T \subset U$ --- множество допускающих состояний, а $\varphi : U \times \Sigma \rightarrow U$ представляет собой функцию переходов.

Входом для автомата является слово $\alpha$, составленное из символов алфавита $\Sigma$. Исходно автомат находится в состоянии $s$. На каждом шаге он читает очередной символ $c$ входного слова и изменяет свое состояние на $\varphi(u, c)$, где $u$ --- текущее состояние. После этого автомат переходит к следующему символу входного слова. Если когда слово целиком обработано автомат оказывается в допускающем состоянии, то говорят, что автомат допускает слово $\alpha$, иначе говорят, что он его не допускает.

Разделим все слова длиной от 0 до заданного числа $n$ на два множества: $S^+$ и $S^-$. Говорят, что автомат соответствует этому разбиению, если он допускает все слова из $S^+$ и не допускает все слова из $S^-$. Заметим, что слова длиннее $n$ могут как допускаться, так и не допускаться автоматом.

Требуется построить автомат, соответствующий заданному разбиению, имеющий минимальное количество состояний.

Первая строка входного файла содержит число $n$ ($1 \le n \le 12$). Следующие $2^{n+1}-1$ строк описывают $S^+$ и $S^-$. Каждая строка содержит по одному слову, перед словом идет <<+>>, если оно содержится в $S^+$, либо <<->>, если оно содержится в $S^-$. Слова упорядочены по длине, а при равной длине --- лексикографически.

На первой строке выходного файла выведите число $u$ --- минимальное количество состояний в автомате ($u \ge 1$) и $s$ --- номер начального состояния (состояния нумеруются от $1$ до $u$).

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

Следующие $u$ строк должны описывать переходы, каждая из этих строк должна содержать по два числа, $i$-я из строк должна содержать $\varphi(i, 0)$ и $\varphi(i, 1)$.