CF1344C.Quantifier Question

Logical quantifiers are very useful tools for expressing claims about a set. For this problem, let's focus on the set of real numbers specifically. The set of real numbers includes zero and negatives. There are two kinds of quantifiers: universal ($\forall$) and existential ($\exists$). You can read more about them here.

The universal quantifier is used to make a claim that a statement holds for all real numbers. For example:

• $\forall x,x \lt 100$ is read as: for all real numbers $x$, $x$ is less than $100$. This statement is false.
• $\forall x,x \gt x-1$ is read as: for all real numbers $x$, $x$ is greater than $x-1$. This statement is true.

The existential quantifier is used to make a claim that there exists some real number for which the statement holds. For example:

• $\exists x,x \lt 100$ is read as: there exists a real number $x$ such that $x$ is less than $100$. This statement is true.
• $\exists x,x \gt x-1$ is read as: there exists a real number $x$ such that $x$ is greater than $x-1$. This statement is true.

Moreover, these quantifiers can be nested. For example:

• $\forall x,\exists y,x \lt y$ is read as: for all real numbers $x$, there exists a real number $y$ such that $x$ is less than $y$. This statement is true since for every $x$, there exists $y=x+1$.
• $\exists y,\forall x,x \lt y$ is read as: there exists a real number $y$ such that for all real numbers $x$, $x$ is less than $y$. This statement is false because it claims that there is a maximum real number: a number $y$ larger than every $x$.

Note that the order of variables and quantifiers is important for the meaning and veracity of a statement.

There are $n$ variables $x_1,x_2,\ldots,x_n$, and you are given some formula of the form $$ f(x_1,\dots,x_n):=(x_{j_1} \lt x_{k_1})\land (x_{j_2} \lt x_{k_2})\land \cdots\land (x_{j_m} \lt x_{k_m}), $$

where $\land$ denotes logical AND. That is, $f(x_1,\ldots, x_n)$ is true if every inequality $x_{j_i} \lt x_{k_i}$ holds. Otherwise, if at least one inequality does not hold, then $f(x_1,\ldots,x_n)$ is false.

Your task is to assign quantifiers $Q_1,\ldots,Q_n$ to either universal ($\forall$) or existential ($\exists$) so that the statement $$ Q_1 x_1, Q_2 x_2, \ldots, Q_n x_n, f(x_1,\ldots, x_n) $$

is true, and the number of universal quantifiers is maximized, or determine that the statement is false for every possible assignment of quantifiers.

Note that the order the variables appear in the statement is fixed. For example, if $f(x_1,x_2):=(x_1 \lt x_2)$ then you are not allowed to make $x_2$ appear first and use the statement $\forall x_2,\exists x_1, x_1 \lt x_2$. If you assign $Q_1=\exists$ and $Q_2=\forall$, it will only be interpreted as $\exists x_1,\forall x_2,x_1 \lt x_2$.

逻辑量词是表达关于集合的命题时非常有用的工具。在本题中，我们专门关注实数集。实数集包含零和负数。量词分为两类：全称量词（$\forall$）和存在量词（$\exists$）。你可在此处了解更多。

全称量词用于断言某个命题对所有实数均成立。例如：

• $\forall x,x \lt 100$ 读作：“对所有实数 $x$，$x$ 小于 $100$”。该命题为假。
• $\forall x,x \gt x-1$ 读作：“对所有实数 $x$，$x$ 大于 $x-1$”。该命题为真。

存在量词用于断言存在某个实数使得命题成立。例如：

• $\exists x,x \lt 100$ 读作：“存在一个实数 $x$，使得 $x$ 小于 $100$”。该命题为真。
• $\exists x,x \gt x-1$ 读作：“存在一个实数 $x$，使得 $x$ 大于 $x-1$”。该命题为真。

此外，这些量词可以嵌套使用。例如：

• $\forall x,\exists y,x \lt y$ 读作：“对所有实数 $x$，存在一个实数 $y$，使得 $x$ 小于 $y$”。该命题为真，因为对任意 $x$，取 $y=x+1$ 即可满足。
• $\exists y,\forall x,x \lt y$ 读作：“存在一个实数 $y$，使得对所有实数 $x$，$x$ 均小于 $y$”。该命题为假，因为它声称存在一个最大的实数：即一个大于所有 $x$ 的数 $y$。

注意，变量与量词的顺序对命题的含义及其真假至关重要。

现有 $n$ 个变量 $x_1,x_2,\ldots,x_n$，并给定一个形如

$$f(x\_1,\\dots,x\_n):=(x\_{j\_1} \\lt x\_{k\_1})\\land (x\_{j\_2} \\lt x\_{k\_2})\\land \\cdots\\land (x\_{j\_m} \\lt x\_{k\_m})$$

的公式，其中 $\land$ 表示逻辑“与”（AND）。即，当且仅当每个不等式 $x_{j_i} \lt x_{k_i}$ 均成立时，$f(x_1,\ldots, x_n)$ 为真；否则（即至少有一个不等式不成立），$f(x_1,\ldots,x_n)$ 为假。

你的任务是为变量 $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 \lt x_2)$，则不允许将 $x_2$ 置于 $x_1$ 之前，即不允许使用 $\forall x_2,\exists x_1, x_1 \lt x_2$ 这一形式。若你指定 $Q_1=\exists$ 且 $Q_2=\forall$，则该命题仅被解释为 $\exists x_1,\forall x_2,x_1 \lt x_2$。

The first line contains two integers $n$ and $m$ ($2\le n\le 2\cdot 10^5$; $1\le m\le 2\cdot 10^5$) — the number of variables and the number of inequalities in the formula, respectively.

The next $m$ lines describe the formula. The $i$-th of these lines contains two integers $j_i$,$k_i$ ($1\le j_i,k_i\le n$, $j_i\ne k_i$).

第一行包含两个整数 $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$）。

If there is no assignment of quantifiers for which the statement is true, output a single integer $-1$.

Otherwise, on the first line output an integer, the maximum possible number of universal quantifiers.

On the next line, output a string of length $n$, where the $i$-th character is "A" if $Q_i$ should be a universal quantifier ($\forall$), or "E" if $Q_i$ should be an existential quantifier ($\exists$). All letters should be upper-case. If there are multiple solutions where the number of universal quantifiers is maximum, print any.

如果不存在使该命题为真的量词赋值方案，则输出单个整数 $-1$。

否则，在第一行输出一个整数，表示可能的全称量词的最大数目。

在下一行输出一个长度为 $n$ 的字符串，其中第 $i$ 个字符为 "A" 表示 $Q_i$ 应为全称量词（$\forall$），或为 "E" 表示 $Q_i$ 应为存在量词（$\exists$）。所有字母均须为大写。若存在多个使全称量词数目达到最大的解，输出任意一个即可。

For the first test, the statement $\forall x_1, \exists x_2, x_1 \lt x_2$ is true. Answers of "EA" and "AA" give false statements. The answer "EE" gives a true statement, but the number of universal quantifiers in this string is less than in our answer.

For the second test, we can show that no assignment of quantifiers, for which the statement is true exists.

For the third test, the statement $\forall x_1, \forall x_2, \exists x_3, (x_1 \lt x_3)\land (x_2 \lt x_3)$ is true: We can set $x_3=\max{x_1,x_2}+1$.

对于第一个测试，命题 $\forall x_1, \exists x_2, x_1 \lt x_2$ 为真。“EA”和“AA”的答案给出的是假命题。“EE”的答案给出的是真命题，但该字符串中全称量词的个数少于我们答案中的个数。

对于第二个测试，我们可以证明：不存在能使该命题为真的量词赋值方式。

对于第三个测试，命题 $\forall x_1, \forall x_2, \exists x_3, (x_1 \lt x_3)\land (x_2 \lt x_3)$ 为真：我们可以取 $x_3=\max{x_1,x_2}+1$。