Логические кванторы — это очень хороший инструмент для создания некоторых утверждений о множестве. В этой задаче мы будем рассматривать множество вещественных чисел. Множество вещественных чисел содержит ноль и отрицательные числа. Есть два вида кванторов: всеобщности (\(\forall\)) и существования (\(\exists\)). Вы можете прочитать больше про них здесь.
Квантор всеобщности используется, чтобы сказать, что утверждение выполнено для всех вещественных чисел. Например:
- \(\forall x,x<100\) читается как: для всех вещественных чисел \(x\) число \(x\) меньше, чем \(100\). Это утверждение ложно.
- \(\forall x,x>x-1\) читается как: для всех вещественных чисел \(x\) число \(x\) больше, чем \(x-1\). Это утверждение верно.
Квантор существования используется, чтобы сказать, что существует некоторое вещественное число, для которого утверждение выполнено. Например:
- \(\exists x,x<100\) читается как: существует вещественное число \(x\) такое, что \(x\) меньше, чем \(100\). Это утверждение верно.
- \(\exists x,x>x-1\) читается как: существует вещественное число \(x\) такое, что \(x\) больше, чем \(x-1\). Это утверждение верно.
Кроме того, эти кванторы могут быть вложенными. Например:
- \(\forall x,\exists y,x<y\) читается так: для всех вещественных чисел \(x\) существует вещественное число \(y\) такое, что \(x\) меньше, чем \(y\). Это утверждение верно для всех \(x\), потому что существует \(y=x+1\).
- \(\exists y,\forall x,x<y\) читается так: существует вещественное число \(y\) такое, что для всех вещественных чисел \(x\) число \(x\) меньше, чем \(y\). Это утверждение ложно, потому что оно утверждает, что существует максимальное вещественное число: число \(y\) больше, чем любое \(x\).
Обратите внимание, что порядок переменных и кванторов важен для значения и верности утверждения.
Всего есть \(n\) переменных \(x_1,x_2,\ldots,x_n\), и вам дана формула вида \(\) f(x_1,\dots,x_n):=(x_{j_1}<x_{k_1})\land (x_{j_2}<x_{k_2})\land \cdots\land (x_{j_m}<x_{k_m}), \(\)
где \(\land\) обозначает логическое И. Это означает, что \(f(x_1,\ldots, x_n)\) истинно, если каждое неравенство \(x_{j_i}<x_{k_i}\) выполнено. Иначе, если хотя бы одно неравенство не выполнено, то \(f(x_1,\ldots,x_n)\) ложно.
Ваша задача — выбрать значения каждого из кванторов \(Q_1,\ldots,Q_n\) либо квантором всеобщности (\(\forall\)), либо квантором существования (\(\exists\)) так, что утверждение \(\) Q_1 x_1, Q_2 x_2, \ldots, Q_n x_n, f(x_1,\ldots, x_n) \(\)
будет верно и количество кванторов всеобщности максимально возможное, или определить, что утверждение ложно для всех возможных выборов кванторов.
Обратите внимание, что порядок переменных, в котором они идут в утверждении фиксирован. Например, если \(f(x_1,x_2):=(x_1<x_2)\), то вам не разрешено сделать переменную \(x_2\) идущей первой, и получить утверждение \(\forall x_2,\exists x_1, x_1<x_2\). Если вы выберете \(Q_1=\exists\) и \(Q_2=\forall\) получившееся утверждение будет однозначно равно \(\exists x_1,\forall x_2,x_1<x_2\).
Выходные данные
Если ни одной расстановки кванторов такой, что утверждение будет верно, не существует, выведите единственное целое число \(-1\).
Иначе на первой строке выведите максимальное возможное количество кванторов всеобщности.
На следующей строке выведите строку длины \(n\), в которой \(i\)-й символ это «A», если \(Q_i\) должен быть квантором всеобщности (\(\forall\)), или «E», если \(Q_i\) должен быть квантором существования (\(\exists\)). Все символы должны быть в верхнем регистре. Если существует несколько возможных решений, в которых количество кванторов всеобщности максимально возможное, выведите любое.
Примечание
В первом тесте утверждение \(\forall x_1, \exists x_2, x_1<x_2\) верно. Ответы «EA» и «AA» дают ложные утверждения. Ответ «EE» дает верное утверждение, но количество кванторов всеобщности будет меньше, чем в нашем ответе.
Для второго теста можно показать, что ни одной расстановки кванторов такой, что утверждение будет верно, не существует.
В третьем тесте утверждение \(\forall x_1, \forall x_2, \exists x_3, (x_1<x_3)\land (x_2<x_3)\) верно: мы можем выбрать \(x_3=\max\{x_1,x_2\}+1\).