C. Задача про кванторы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Логические кванторы — это очень хороший инструмент для создания некоторых утверждений о множестве. В этой задаче мы будем рассматривать множество вещественных чисел. Множество вещественных чисел содержит ноль и отрицательные числа. Есть два вида кванторов: всеобщности ($$$\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$$$.

Входные данные

В первой строке находятся два целых числа $$$n$$$ и $$$m$$$ ($$$2\le n\le 2\cdot 10^5$$$; $$$1\le m\le 2\cdot 10^5$$$) — количество переменных и неравенств в формуле, соответственно.

Следующие $$$m$$$ строк описывают формулу. $$$i$$$-я из этих строк содержит два целых числа $$$j_i$$$, $$$k_i$$$ ($$$1\le j_i,k_i\le n$$$, $$$j_i\ne k_i$$$).

Выходные данные

Если ни одной расстановки кванторов такой, что утверждение будет верно, не существует, выведите единственное целое число $$$-1$$$.

Иначе на первой строке выведите максимальное возможное количество кванторов всеобщности.

На следующей строке выведите строку длины $$$n$$$, в которой $$$i$$$-й символ это «A», если $$$Q_i$$$ должен быть квантором всеобщности ($$$\forall$$$), или «E», если $$$Q_i$$$ должен быть квантором существования ($$$\exists$$$). Все символы должны быть в верхнем регистре. Если существует несколько возможных решений, в которых количество кванторов всеобщности максимально возможное, выведите любое.

Примеры
Входные данные
2 1
1 2
Выходные данные
1
AE
Входные данные
4 3
1 2
2 3
3 1
Выходные данные
-1
Входные данные
3 2
1 3
2 3
Выходные данные
2
AAE
Примечание

В первом тесте утверждение $$$\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$$$.